Now that I'm at home I can add that the earliest known edition is in the Shirburn Ballad collection ( online facsimiles at the Internet Archive ) where there is also a sequel, 'A merry ballad of the miller and king Henry the second; shewing how he came to court...' (also reprinted in Roxburghe Ballads I, 543) to the same tune.

The tune originally specified was 'The French Levalto': Simpson (The British Broadside Ballad and Its Music, 237-8) prints an example of notation from an English MS in the Paris Conservatoire, but it isn't a good fit with the text and would require some modification. Chappell (Popular Music of the Olden Time, I, 169-170) prints a form of the tune from Rimbault's Musical Illustrations of Percy's Reliques, set to the 'Miller of Mansfield' words and with a modern harmonization; so you could sing it if you had the time and the stamina and an unusually patient audience.