In the strictest sense, the older verifiable direct ancestor of Charlemagne was Arnulf of Metz, the founding figure of the Arnulfian (or Arnulfing) line and the parternal great-grand-father of Charles Martel.
We don't know much about him, however, and what we do comes from two hagiographies (both named Vita Arnulfi, or Life of Arnulf) and genealogical mentions scattered all over the IXth and Xth centuries.
The first V.A. (along with precision by Paul Deacon about the great nobility of his family) describes him as issued from a powerful family of Austrasia, particularly in modern Lorraine. As expected he received a strong instruction in classical and religious education, is part of the royal palatial network in the sub-kingdom under the majordomo Gundulf due to his military and administrative skills (as well as, possibly, his familial origins) and have to renounce a religious undertaking under familial pressure. He marries a "very noble woman" (called Doda in the second V.A.) and from the union were issued Clodulf and Anchises (the grand-father of Charles Martel). Having supported Clothar II in the unification of sub-kingdoms, he's named as Bishop of Metz, which is both a religious and administrative function, while keeping his palatial functions, before eventually adopting a monastic life shortly before his death.
On the origins of Arnulf, we don't know anything really explicit at first, except he was born from a "powerful and noble Frankish family". Later genealogies provided with more details but without much coherence and with conflicting narratives which anarchically tried to display the oldness and prestige of Carolingians, especially as the "self-made saint/aristocrat" model becomes really popular with the VIIth century.
There's essentially two different genealogical traditions from medieval accounts.One, traditionally held, making Arnulf the son of Arnold of Metz, the great-nephew of Aigulf and the grandson of Anspert "of senatorial upringing", being thus twice issued from Merovingian by women and related to the Gallo-Roman familial network of Ferreoli and Syagrii.These genealogies were unsurprisingly made in Metz relatively early on from the VIIIth century, as Carolingians were the ruling family in Austrasia and were about the cement their rule over the whole of Francia. Asserting a really prestigious ascendancy, it nevertheless have several issues, probably due to interpolation of documents, chronological anarchy (some individual are supposed to be grand-fathers of peoples of a same generations, for instance) and desire to display the ancestors of Charlemagne in the best of light.
Another tradition, with more scattered around accounts both geographically (one being found in England) and chronologically (such as the Vita Gundulfi of the XIIth century) along with genealogies made at Fontenelle, likewise with a mess of generational and folkloric mix-up, but introducing plausible clues based on onomastics and what we otherwise know of Arnulfians.It would make Anulfians more or less directly issued from the petty-kings of Cologne, particularly from Cloderic whose descendance would have been less prestigious in the eyes of Metz' chroniclers if they had a clue about Arnulf's origin, which is not at all a given as they might have confused a tradition of Frankish royal origin with a Merovingian origin.Arnulf's father would be thus Bodogisel, probably the ambassador killed in Carthage and his grand-father would be Mummolinus, son or son-in-law of Munderic, son or otherwise related to Cloderic. Mummolinus bearing a partly Roman looking name might have been furthermore issued from a Roman family. Arnulfians would be then originating from Rhineland, eventually established in Lorraine after having occupied functions in Neustria and southern Gaul, having lost royal prestige, and probably knowledge of its origin then. It's, eventually, possible that Arnulf was related to Arnoald by marriage, his own or his father.
What can be said is that Arnulf, eventually, is that his family was of no uncertain importance in the region, altough overshadowed by Pippinids.
As with Arnulfians, we don't really know the origin of Pippinids : Pepin the Elder (also known as Pepin of Herstal) is said in a contemporary source to be "from such an illustrious family that it can't be unknown to anyone", without any more information which makes their origin essentially lost to us. It's still hypothesized, giving the relation of Pippinids and later Arnulfians with Bavaria, that the former were genealogically related to Agilofinges that ruled the region.Pepin the Elder himself had a similar life to Arnulf, minus the attraction to a religious life, and became majordomo of Austrasia, and Pippinids became the leading lineage in the region, to the point Dagobert tried to curb down aristocratic ambition there by removing both aristocrats out of their functions, which had little lasting impact on their familial power.The marriage between Anchises, the son of Arnulf and a daughter of Pippin called Begga cemented the alliance between two families and as Grimoald, Anchises' brother-in-law was executed after a very unclear gamble for royal control in Austrasia, descendants of Arnulf "inherited" his prestigious familial and aristocratic network and eventually adopting for themselves their genealogical names, especially Pepin, hence why Arnulfians are often called Peppinids themelves.
EDIT : Tracing the origin of high medieval families, including Carolingians, remains difficult. Several lines might simply have emerged out of the aftermath of the royal faida, with the extinction or important losses in Franko-Romans families along with the emergence of lines that far from hiding their recent rise to power and notability as it was still done in the VIth century, celebrated self-made aristocrats/saints as their ancestors (especially when, ironically, they might have been issued from older lineages).
Descent from Antiquity is thus difficult, maybe even impossible, for these families : eventually the emergence of an "imperial" aristocracy counting maybe 50 to 60 families for the whole kingdom by Carolingians might have represented yet another rupture with Late Ancient/Early medieval aristocracy.
Christian Settipani, probably half-jokingly, said that Charlemagne could arguably be related to Diocletian who might have been the father-in-law of the father-in-law of the uncle of the father-in-law of the half-brother of the great-grand-mother of the second wife of the brother-in-law of the the grand-father of the brother-in-law of the great-great-great-great-great-great-great-grand father of Charlemagne's wife.Of course, at this point, descent from Antiquity loose most relevance to joyfully embrace absurdity.