To sum up my best thinking about the origins of our name and about our eponymous ancestor, we have to go back to the 6th/7th Century Celtic saint 'Mochuda Carthach'. His name means simply 'loving one'. In Ireland his 'surname' or 'clan name' has been anglicised, via the Latin form Carthagus, as Carthage, and also has been abbreviated to Carthy. Followers have spawned a number of variants, such as McGillycuddy and McElhuddy. Parallel to this evolution we have what appears to be a migration to the south-west of Scotland, possibly a very early migration in the same Celtic period, using his 'pet' name Mochuda, via the Latin follower-form Gilmagu, evolving into McIlhago and McIlhagga. The meaning is of course the same, 'son of the devotee of the loving one'.
My American correspondent searched for 'Gilmagu' in Black's Surnames and found of course the MacIlhagga reference that '(p)art of the lands of ffincurrokis were granted to Gilmagu and his heir c. 1160-80', recorded in the annals of the Abbey at Kelso in the Scottish Borders (see my blog of 8 Feb 2009). He also found another relevant historical reference, that the named witness to this transaction was one 'James de Draffon or Drafon, from the lands of Draffon, near Lesmahagow, Lanarkshire. Between 1160 and 1189 he (James) appears several times as a charter witness in the chartulary of Kelso' (Black 220). Black points out that in another charter Gilmagu is mentioned as Gilmagu mac Aldic and he is most probably Gilmalgon (evidently a miscopying of Gilmahgou) mac Kelli, who witnessed Abbot Arnald's gift of the lands of Duueglas (Douglas) to Theobald the Fleming, c. 1150 (again, see 8 Feb 09).
As a final point of interest and comparrison for today, in contrast to the Scottish derivation McIlhagga being one of the rarest surnames in the world, I may quote Edward MacLysacht, in The Surnames of Ireland, that Carthy, or rather MacCarthy, 'the chief family of the Eoghanacht and one of the leading septs of Munster, prominent in the history of Ireland from the earliest times to the present, is the most numerous Mac name in Ireland'.