Although widely printed in the 19thc I have no versions earlier than the early 19thc. Most versions have a standard 10 stanzas and start 'A story unto you I will relate' but there were 2 12-stanza versions printed in the North East by Marshall of Newcastle and Walker of Durham (the Marshall probably the earlier) that start 'I'll tell you of a worthy knight'. Yes I agree it sounds vaguely like an earlier piece but towards the end of the 18thc there was a lot of writing of faux medieval pieces for pageants and plays, and there is a pretty good chance this is where it came from.