From Ireland and Scotland
There is, nearly always, more than one source of an Irish or Scottish surname. McCullough is no exception. And there are many, many spelling variations of the name.
I found many sources of the McCullough name, although two are the most credible, at least to me.
One derives from a 9th Century guy named Cullagh. He was from the coastal Galloway region in the Lowlands of Scotland, across the channel from Ireland. “Galloway” is the English phonetic spelling of the Gaelic word for “foreign Gaels”. It was applied to the folks in the region with both Gaelic Scottish and Viking Scandinavian heritage.
When descendants of Cullagh began adopting surnames, many took the name “MacCullagh” or “son of Cullagh”. More than a few MacCullaghs and MacDonalds intermarried over the centuries, and the two clans were usually allied.
Most Scots from the Lowlands, including the MacCullaghs, became Presbyterians during the Reformation. And many of these MacCullaghs settled in Ireland during the Ulster Plantations of the 1600s.
Another source derives in Ireland from the name Cú Uladh, meaning the “hound of Ulster”. This may seem strange today as a first name, but it was not at all unusual as a first name in pre-medieval Ireland. The sons of Cú Uladh became Mac Cú Uladh, and the surname was ultimately spelled McCullough (or its many variations) in English.