Cailleach is derived originally from caille (veil) which is in itself derived from the Latin "pallium" indicating that the term came into gaelic with the arrival of christianity. The rendering of initial Latin p- as c- in gaelic is regular in that early period. Cailleach used for an old woman or hag is evidenced in early writings however and the cailleach in Irish literature and folklore is the subject of a book due out about now in Ireland.   This doesn't have much to do with Moll Dubh an Ghleanna but may interest those who have been looking up the modern dictionaries.

Cailleach dhubh or broigheall is what my grandfather used to call a cormorant, a bird he used to shoot and eat. Not a dish found in many Irish restaurants nowadays.