You've heard of "Charlemagne", and you've heard him mentioned as "Charles the Great" and even "Carolus Magnus" in Latin. These names are, obviously, all equivalent, but he would have answered to none of them. He was a Frank, and spoke Frankish until the day of his death. (His biographer and close friend, Einhard, says that Charlemagne investigated learning Latin, but decided not to do it.) He hired diplomats to speak in Latin for him.
His name, in the only language he ever knew, was simply "Karl". The Frankish language is a dialect of German, and a modern version of it is still spoken in the homeland of the Franks. This region, Frankenland (or "Franconia" in English), constitutes the northern half of the modern province of Bavaria. As his reputation grew, he became known as "Karl der Grosse" (properly "Karl der Große"), meaning "Karl the Great".
His people, the Franks, left their name on city of Frankfurt, which means literally "the ford of the Franks", because that is where the Franks crossed the river during the era which we call the "migration of peoples" (historians call this the "Völkerwanderung"). There are actually three towns named "Frankfurt", separated by several hundred miles. By these town names, one can re-trace the route of the Franks during the Völkerwanderung. Even Michigan has its Frankenmuth. The nation of France also bears the name of this Germanic tribe - a bit of irony!
Could it be that he became known as "Charlemagne" or "Charles the Great" because French-speaking and English-speaking historians didn't want to admit that the first and most powerful central European empire was formed and ruled by a German?