I've read in another reddit thread that he spoke Old High German natively and that this language was important to him since he ordered/encouraged people to not only write books in Latin but also in Old High German. Therefore I'm really interested in what he called himself in inner monologues and what people of his home region called him. It's even more interesting as his name is ironically widely known in a dozen languages other than his native one. I already found out that 'the'='der' and 'great'='groz', but unsure how to nominalize 'groz' properly and which version of Charles (Carl/Karl/Karel/...) is correct. First try: 'Carl der grozze'. Second try (thanks /u/Zither13): 'Kerl der grozze' (still unsure about 'grozze').
Also: was Charles a chosen name when he became a king (i.e. like popes choose their names)? If so, what was his name when he was a child? Answer (thanks /u/Whoosier): he didn't have another name.
I can answer some of this. In childhood he was Karl, just as his grandfather had been. His name didn’t change upon his coronation. Remember that “Charlemagne” is simply a compressed version of the French “Charles le Magne,” itself a translation of the Latin “Carolus Magnus” or “Charles the Great.” Latin was the official written language of his day (though he was interested in preserving Old High German literature). I’m not sure there are any Old High German sources, which are scarce in any event, that call him “Charles the Great.” The earliest use of the title I know of is in the Latin Royal Frankish Annals in the account of his coronation as Roman Emperor in 800. The people acclaim him: “To Charles Augustus, great and peaceful emperor crowned by God, life and victory!” (Carolo augusto, a Deo coronato magno et pacifico imperatori Romanorum, vita et victoria!). By around 865 he is being called “the Great” in the Visio Karoli Magni (Visio of Charles the Great). The Old French Chanson de Roland usually calls him “Carlemagne.” (The first line of the poem is “Carles li reis, nostre emper[er]e magnes”—Charles the king, our great emperor.”) But the poem dates at the earliest from the mid-eleventh century. One place to see the name “Karl” bouncing from Latin, to Old High German, to Old French is the famous [Oath of Strasbourg] (https://en.wikipedia.org/wiki/Oaths_of_Strasbourg) of 842 between his grandsons Charles and Louis.
Someone versed in Old High German will have to put his name into that language for you. Some people probably called him that in his native language in or after his day, though I’d be surprised if it ever got written down.
He answered to Kerl, the older form of Karl. Whoosier told you about the title business.
Ingraham, People's Names, Frankish chapter.
I have a related question. I was reading a book recently and somewhere it claimed that Charlemagne was called "David" by close associates. Is there any truth to this?