Whether it's a translation of lost sources or primarily a compilation of lore based largely in ones we know is unclear (it's most likely a little of both), but the Old Norse Karlamagnussaga, or "Saga of Charlemagne," is one of the best sources we have for how medieval legend portrayed Charlemagne - all presented in the way that legend was shaped for presentation to a Scandinavian audience.
The most important aspects of the Matter of France are two related pieces of mythologized history: the double conquest of most of Spain by the Franks, and the death of Roland during an attempt to capture the last little piece the second time around. Both of these stories are presented to us first in the high middle ages, and both appear in the Karlamagnussaga in a form consistent with the French sources. (The former appears, in a much distorted form, in the late Italian epic poems Orlando Innamorato and Orlando Furioso; given that these revolve around the character of Roland, it's unclear whether the Innamorato, left unfinished at its author's death, was originally meant to continue to the point of telling the second story as well.) As in the Latin-language pseudo-Turpin chronicle, a high medieval French document which purports to have been a firsthand account of Charlemagne's life penned by the Archbishop Turpin, we are told how Charlemagne conquered all or most of Spain before the Saracen king Agolant took it all back from him; Charlemagne then retakes it only after Agolant's death. (It's not clear how the author of the pseudo-Turpin intends us to reconcile this with the fact that half of Spain is split between feuding Muslim states at the time of his writing.) It is at the end of this war, one presumes, that the events of the Chanson de Roland occur.
Another major story, of course, is the death of Roland. This occurs, not merely in a manner consonant with the other traditional sources, but in what appears to be a loose prose translation of a known extant text of the the Chanson de Roland. Clearly, in telling the life of Charlemagne, the battle of Roncesveaux as presented in the greatest of the chansons de geste is not an optional detail.
We're also treated to a number of other stories also known from forms found in Old French. But perhaps the most intriguing is the story of a young Charlemagne's adventures with the master thief Basin, during which the two defeat two traitors who intended to kill the king. The two traitors seem to be echoes of two historical figures - but not ones from Charlemagne's lifetime. Rather, the real-world Chilperic and Ragenfrid betrayed the historical Charles Martel, and he defeated them before his even more illustrious grandson was ever born.
I find this fact fascinating because it is one of several examples of the entire Carolingian period apparently being compressed by myth into the life of one singular and impossibly great king. When one considers everything Charlemagne accomplished in reality, it's impressive; when you fold in the victories of Charles Martel (apparently moved across the Pyrenees, as the first part of Agolant narrative) and some of the life of Charlemagne's descendants, make dukes such as Waifer of Aquitaine into staunch vassals (Count Gayferos), and further add imaginative details which make the stories much more impressive than their real-world counterparts, the result is a royal figure larger than life, one who seems to belong as much to a precursor to the tall tale tradition as to heroic supposed history. And yet, these stories are told to us in documents which purport to be accurate accounts of what is said to have genuinely happened - and these accounts, which so beggar credulity, spread to the far corners of Europe, hence the preservation of the Basin tale in Scandinavia.