Most people do not get their epithets during their lifetimes. However, Charlemagne was pretty close. Based on my reading he does not truly get the epithet until a few decades after his death, so by about 840 is when it becomes fairly common to see him referred to as Karoli Magni. Before then he is usually just referred to as Charles (Karolus), David (it was a nickname among some of his inner circle) and usually he would have some type of title with him (augustus, rex, patricius, etc.) This is pretty common in the Royal Frankish Annals, the nickname generally came from Alcuin, his court scholar, and the Karoli Magni shows up in compilations of early sources around 840. So compilations of the annals would distinguish the section relating to Charlemagne by referring to it as the "Gesta Domni Karoli Magni" or something similar (see Rosamond McKitterick's article "Political Ideology in Carolingian Historiography")