This is an interesting question. Mythology and folklore tend to be expressed in the vernacular. Anglo-Saxon England is perhaps the greatest example of this mixture between Christian and "pagan" values which your question hints at.^1 Texts such as The Dream of the Rood present an interesting response to Christian themes of self-sacrifice, whilst other, more overtly native, texts (Beowulf, The Battle of Maldon, etc.), come close to "mythology" or "folklore". In respects to the Carolingians, the short answer is that no significant literary remains (in the vernacular) survive. Latin texts, however, are plentiful and do hint at a Germanic-style literary background, perhaps matching the rich remains of Anglo-Saxon literary culture, although it is incredibly hard to be accurate about its contents. There are hardly any texts in Frankish, the language of the Carolingian elite and most of their subjects, and it is tempting to suggest that there never was. Like Wales in the sub-Roman period, elite entertainment, the hot-house for the development of "native" literatures, was likely in Latin.^2 Roman culture was incredibly influential on Carolingian society.

Plenty of societies hundreds of years after Charlemagne enjoyed what was called "The Matter of France", a series of tales detailing the exploits of Charlemagne stemming from the Chanson de geste of the twelfth and thirteenth centuries. These tales stood alongside "The Matter of Britain" (King Arthur) and "The Matter of Rome" (classical material). The Song of Roland is an example of one of these chanson. In fact, many argue it as the earliest major work of French literature.^3 It covers an historical ambush of Frankish troops by the Basques in 778; it's covered in the Royal Frankish Annals as well as Einhard's Life of Charlemagne. Nevertheless, even this early work does not date before the new millennium. A few saints lives do date from the ninth century (e.g., Saint Eulalia and Saint Alexis), though their relevance for your question is limited. As you might note, all of these works are in Old French, not Frankish, and when they do describe Carolingian society, there is little in the way of eighth or ninth century myths and legends. Latin was the written language of Gaul from Caesar to the chanson. Chronicles, hagiography, charters, none of these records were in Frankish. Even something as native as law was written in the lingua franca of the day, Latin. Frankish is so badly attested that it has to be reconstructed from loanwords and modern Dutch.^4

To answer your question, then, we must compare Frankish society with its Germanic cousins (a task with many pitfalls) and scrape together what references there are in contemporary Latin, and later French, texts. Archaeology might tell you about early Germanic pagan ritual - although this naturally does not relate to the fully Christian Carolingians, but their Frankish ancestors. I'm afraid that learning about Carolingian legends is a work for literary reconstruction, not casual reading. I would speculate that myths and legends were indeed told amongst the Franks, perhaps even the Carolingians, but that they did not have the same relevance as Old English legends at the court of someone like King Alfred. Here's a little comparison to illustrate the difference:

The Life of King Alfred, written by the Welsh monk Asser in 893, states clearly that its subject was "ignorant of [Latin] letters until his twelfth year, or even longer. However, he was a careful listener, by day and night, to English poems, most frequently hearing them recited by others, and he readily retained them in his memory".^5 There follows a story where Alfred's mother hands him and his brothers a book of Old English poems, stating that he who might learn them by rote might keep the book. Of course, Alfred is great and does it straight away. We might compare these early events in Alfred's life with his urge later on to translate those books "most needful for men to know" into English.^6 The vernacular was important in England, and native myths and legend were learned by heart by the nobility and, one assumes, by those who composed them. Now, Asser's Life is heavily based on Einhard's Life of Charlemagne.^7 However, in the latter no mention is made of vernacular literature. Charlemagne also initiated an important reform program; though unlike Alfred's later efforts, this was almost entirely focused on Latin.^8 The relative importance of Latin and the vernacular will always be uncertain, yet it is not far of the mark to suggest that this cultural emphasis covered many native Carolingian myths and legends.

In conclusion, if you want great myths and legends, look at the Anglo-Saxons. Here are some books to get you started:

Bradley, S. A. J., Anglo-Saxon Poetry (1982)

Marsden, R., The Cambridge Old English Reader (2004)

*Godden, M., ed., The Cambridge Companion to Old English Literature, 2nd Edition (2013)

An edition of Beowulf (check out Heaney for a literary translation or the one in Bradley above).

^1 Frank, 'Germanic Legend in Old English Literature', and O'Keeffe, 'Heroic Values and Christian Ethics', both in Cambridge Companion to Old English Literature, referenced above.

^2 What language people were speaking shortly after the Romans left is a heavily debated topic. For Wales, see the relevant section in Charles-Edwards, Wales and the Britons, 350-1064 (now in paperback!). There are more specialist articles; if you're interested, PM me.

^3 Old French is not my speciality, I'm afraid. Wikipedia is very good here; see also Cambridge Companion to Medieval French Literature and the bibliographies within the respective articles.

^4 Check out the fantastic book Robinson, O., Old English and Its Closest Relatives, in particular the section on Old Low Franconian.

^5 This is sections 22 and 23. For a superb edition by an old supervisor, see Lapidge and Keynes, ed. and trans., Alfred the Great (1983). It's a Penguin Classic and includes a load of other interesting material on the reign of King Alfred.

^6 This quote is from the introduction to Alfred's translation of Gregory the Great's Pastoral Care. This too is in Lapidge and Keynes.

^7 Check out the footnotes and introduction in Lapidge and Keynes as well as in Ganz, D., trans., Einhard and Notker the Stammerer: Two Lives of Charlemange (2008). Also a Penguin Classic.

^8 For the so-called Carolingian Renaissance, Janet Nelson's work is a great introduction. See also the texts collected in Dutton, P., ed. and trans., Carolingian Civilization: A Reader.

Short answer: yes. Einhard's Life of Charlemagne notes that Charles had the "old songs" and "deeds of ancient kings" written down for posterity (section 29). The Carolingian monastery of Corvey (and likely many others) had murals of Greek/ Roman mythology -- See Lawrence Nees' Tainted Mantle for more. In addition, supposedly Louis the Pious' palace at Ingelheim had murals depicting the great deeds of Louis' predecessors.

The Carolingians were very conscious of their past, particularly in that they were attempting to shape it so as to influence how they themselves were remembered.