I'm not sure about Irish but in Scots Gaelic the spelling of the former is maol.

You are correct that both have ecclesiastical associations but their origins are quite different.

Maol (bald or bare) is also the term used for a monk's tonsure and so the early ecclesiastical use would I presume have been associated with ecclesiastical groups that adopted that feature.

Gillie (lad, man-servant, follower etc) has a much broader use and many a Gillies, MacLellan etc will be descended from people with no ecclesiastical connection.