Sure, definitely possible. Songs in the middle ages were barely, if ever, written down. They were composed orally, taught orally, and performed orally. "Nomadic" jongleurs (minstrels) would travel through towns, villages and courts singing those songs.

Indeed, the actual practice—the actual performance, that is, of the noble songproduct—was usually left to what we now call minstrels: professionals of a lower caste, singer-entertainers called joglars in Provençal (jongleurs in French, both from the Latin joculatores, “jokers”); the derivation of our English word “juggler” from joglar should leave no doubt about its subartistic connotation. Most of the commoner-troubadours like Bernart started out as minstrels who learned the work of the noble poets by rote and who later developed creative facility in their own right. The relationship of troubadour to minstrel, and particularly the means of transmission from the one to the other, attest that the art of the troubadours remained an oral art. A noble poet would compose a song and teach it to a minstrel, thus sending it out into the oral tradition from which it might be transcribed, with luck, a hundred years later. For written documentation of the troubadour art began only when the tradition was already moribund. The manuscripts containing troubadour songs, called chansonniers, are retrospective anthologies prepared in the middle of the thirteenth century. (Any song found in multiple copies in these late sources exists in multiple variants, thus precluding the restoration of a definitive “text,” assuming there ever was such a thing.)

from: Oxford History of Western Music by R. Taruskin, vol1 (I have the kindle version so I cant reference pages)

Some of these songs later became popular folk tunes that were still played in a recent past, thus surviving (orally!) for centuries.

From the same source

POPULARIZATION, THEN AND SINCE The other way in which we know Neidhardt’s songs were popular is that some of them have actually become folk songs. That is, they have rejoined the oral tradition, and were unwittingly collected (in considerably altered form, of course, but still recognizable) by the early folklorists of the German Romantic movement in the eighteenth and nineteenth centuries.

Moreover you can find single references of songs in different parts of europe. North Italian poets like Dante were very aquainted with french/provencal music. Also, as quoted above, most of the written forms of these songs we have today were actually written down way later than the original date of composition. This is a proof that these songs somewhat remained popular for a very long time, or at least known in a form or another.

Some songs also had a bilingual version. For example "Ja nus hons pris" written by none other than Richard Lionheart was known both in an old french version as well as provencal one. Only the french version survives today. I suggest you to listen to it because it is absolutely beautiful https://www.youtube.com/watch?v=lJEZ4ODUuk4 you can easily find and english translation of the text via google

To sum it up: songs widely circulated during the middle ages. They would've been known both by the richs as well as the folks. That doesnt mean english peasants were singing in french, or that they would know exactly the same version as someone living in france or germany. These songs were popularized orally and like every oral art they went through countless variations: in language, performance, minor (and probably major aspects as well) aspects of melody. And so on.