This use of an adjective is called an epithet or byname, or if you want to get technical about it, the Latin term epitheton necessarium. That simply means the epithet is necessary to specify which particular person is meant. Grammatically, it is considered a restrictive appositive.
English and French Charlemagne is actually a contracted form of the French Charles le Magne, Charles the Great. This tells you that even non-contracted forms of such epithets function as proper names.
Just like proper names, epithets are always capitalized:
Alexander the Great, Richard the Lionheart, Henry the Eighth, Charles the Fat, Charles the Bald
These last two Carolingians should also tell you that most but not all such epithets become popular after the death of the ruler so designated.