Don't forget folklore isn't a static thing. I don't just mean individual items being altered in an oral tradition, I mean changing fashions and ideas. Whilst some pieces of folklore last for centuries, others come and go rapidly within a generation. Even in today's so-called advanced society folklore is still being created all the time.
The ballads as we know them weren't around in the 13th century. They seem to have been largely created after 1500 though some of their stories are undoubtedly earlier.

>>>the need for the new words to fit to the metre of the tune<<<
I don't think this would have been a massive problem. Some ballad metres are pretty much universal and there are only about 3 or 4 common ballad metres in English language ballads.