The name certainly comes from the Gaelic element "cath", from Indo-european kéh'tus, but I'm not so sure about the "val" element, mainly because I can't find any etymology. Aside from that, you'd have to be completely fried in the brain to think that a name that has been borne by numerous chieftains and local kings of Ireland before the birth of Jesus sounds Catholic or even Christian- and even more to somehow deduce that something is Christian because it's Irish- surely Irish Gaelic was not the tongue used by Celtic pagans, as opposed to the English used by protestants and caths...
One of the most famous bearers of this name must be Cathal Brugha (1874-1922, born Charles Burgess), an Irish revolutionary politician and freedom fighter, active in the Easter Rising as well as the Irish War of Independence and the Irish Civil War.
Seeing that my name is Cathal I feel I have the right to comment on it. For children the name is impossible to pronounce leading to comical abbreviations such as Cockles. Also as it is an Irish name people from other countries often have trouble with it, leading usualy to you having to spell it for them. But it is for this reason, the Irishness of the name, that I love it.