Part of the problem is that there are only handful of English-language folksongs that have survived from the Middle Ages (which are usually reckoned to have ended by 1500).

"Sir Patrick Spens" may have begun before 1500, but it might well be an 18th Century creation. The same is true of "The Battle of Harlaw."

"Lord Randall" seems to be based on an early Italian song.

Other examples might be "Riddles Wisely Expounded," "Lady Isabel and the Elf Knight," and "The Elfin Knight." Robin Hood song go back before 1500, but the few that survive today also seem to of later composition.

"Lady Isabel" might be a good choice because it was the subject of a book-length study by Holger Nygard called "The Ballad of Heer Hallewijn" (1958). I can't remember if European versions are really "medieval" but they're centiries old.

"Judas" existed only as a poem in a medieval manuscript. John Jacob Niles claimed that he'd collected not one but two versions of it as sung in the Appalachians in the early 20th century. Not everybody believes these songs are actually survivals of the medieval "Judas."

Anyway, good luck!