I don't have time to look far into this just now, but can tell you for a start that there are -or were- a lot of quite widely differing versions of this song.  William Chappell commented in his Popular Music of the Olden Time (1859):

"If I were required to name three of the most popular songs among the servant-maids of the present generation, I should say, from my own experience, that they are Cupid's Garden, I Sow'd the Seeds of Love, and Early One Morning...  The tune... was, I believe, first printed in my collection of English National Airs (1838-40); but the words are contained in many old song-books, such as Sleepy Davy's Garland, The Songster's Magazine, &c.  ...it is curious that scarcely any two copies agree beyond the second line, although the subject is always the same..."

He prints the tune, and the lyric that is known today, together with parts of other versions which apparantly date from the late 18th century.  I don't know anything about the songbooks he mentioned, though Bruce Olson probably would.

There are a number of broadside examples at  Bodleian Library Broadside Ballads,  all apparantly of the first half of the 19th century.  I doubt if the song is earlier than the mid-18th century, but I'm no expert on such things.  It may perhaps have earlier antecedents, but Tudor looks on the face of it like a very large exaggeration!