Charlemagne is widely regarded as a splendid fellow, and he certainly enjoyed great success. His empire (he was crowned Emperor of the West on Christmas Day 800AD) covered France, Germany, Italy and some of Spain (roughly 2/3 of the old Western Empire). He did not manage to eject the Saracens from Spain, but instead preferred to conquer much of Germany.
Charlemagne enjoyed a healthy inheritance of royalty and military might, as his father and grandfather had both been skilled military leaders as well. However, after him the Carlovingian line (which took over from the Merovingians) faltered and then failed quite quickly. The empire was split, and the powerful domains were not reunited again.
Attila’s generally seen as wicked, because he spent much of his time menacing the Roman Empire, as barbarians of the 5th century did rather a lot. He built up an absolutely massive army, comprised greatly of allied tribes who either freely offered manpower as a sign of allegiance or had been forced into so doing.
The defeat of the Huns was actually slightly reminiscent of Antigonus Monopthalmus, the Diadochus whose predominance of power in the 4th century BC encouraged his rival Diadochi (Lysimachus, Cassander and Seleucus) to combine their forces to try and bring him down. The Visigoths, who had control of Gaul, joined armies with Aetius (a Roman general) and managed to defeat the Huns at the Battle of the Catalaunian Plains. Attila died two years later (possibly due to drinking too much), and his great domains and military forces consumed themselves as his sons battled for control amongst themselves.
Both men were skilled military leaders who accrued great power, but after their deaths their legacies did not last long. Charlemagne split his territory amongst his sons, and though Attila had intended one son to succeed him (a more sensible policy) this did not occur. A state that is synonymous with a single leader cannot be stable, especially if it’s subsequently split into multiple states amongst succeeding brothers. Even the mightiest of empires can quickly disintegrate without sound foundations (Alexander’s unified empire fractured almost the moment he died).
On a longer scale, we see the same thing happen with Rome. During its Republican period soldiers were loyal to the state, and a soldier was synonymous with a citizen. After the Marian reforms and then the shift to an empire, soldiers became loyal to generals and emperors, which led to a great deal of infighting. There were times this stopped (the Flavian dynasty and the Golden Age from Nerva to Marcus Aurelius) but Rome was never able to regain her old form. Success depended on having a good emperor and good fortune, but the empire was hooked on regicide.