He has been known as "Attila The Hun" for centuries; however, who originally described Attila as "Attila The Hun"? Does this description date back to Roman times or was it invented during a later historical period? If so, which period?
The precise wording Attila the Hun in English has been in use for at least a couple of centuries but its use in academic writing (at least) was somewhat inconsistent until fairly recently.
The earliest use of Attila the Hun I've found is in William Julius Mikel's introduction to his 1776 translation of The Lusiad by Luis de Camoes. In the same sentence, he also uses Alaric the Goth. The peom itself, though, only uses Attila.
Edward Gibbon used it in volume 12 of The History of the Decline and Fall of the Roman Empire in the 1789 (new edition, but it probably also appears in an earlier edition). However, whereas Attila King of the Huns appears 15 times, Attila the Hun is used only once (out of a total of 39 references to Attila).
Attila the Hun also appears in a 1915 translation of Jordanes, but not in J. B. Bury's The Invasion of Europe by the Barbarians from 1928, nor in E.A. Thompson's History of Attila and the Huns from 1948.
There are, of course, numerous references to Attila the Hun by non-historians and in popular culture, one of the best known being Leadership Secrets of Attila the Hun by Wess Roberts, originally published in 1985. The calypso musician Raymond Quevedo went by the name Atilla the Hun (no, this not a typo - he used one 't' and double 'll') from at least the 1930s, maybe as early as 1911.
Concerning the popular (but basically nonsensical) expression to the right of Attila the Hun, this site says:
The phrase is often associated with Arizona Republican Senator Barry Goldwater (1909-1998), but it is not clear when he first used it. The “Ivan the Terrible” version is cited in print from 1961, the “Genghis Khan” version from 1965, and the “Attila the Hun” version from 1969.