I searched on the subscription site Roots Ireland and as you already found out there are no baptismal records for Catherine Early and Michael Kerrigan/Corrigan in Co. Mayo in the early 1840s. Many Mayo RC parishes have records starting after 1840 and likely your ancestors were baptized in one of those parishes.
The 1855 Griffiths Valuation may provide some leads but there are disclaimers. First, Peter Kerrigan/Corrigan and Michael Early may have moved to England doing the Famine with their families or if they stayed in Ireland they may have died pre-1855. Also, even if they were in Ireland that may not have leased land and for all these reasons may not have been on the Griffiths. See the list below. The word after the first name is the townland followed by the civil parish.
Have you considered DNA testing? You may matches which will provide more info on these lines.