I searched the Irish Family History Foundation's database. It contains 12,000,000 surviving rcds for abt 65% of Irish counties. Rcds are increasingly sparse B4 1840, rare B4 1800.
Note 1 - Without a KNOWN parish, the chance of an ancestor's rcds NOT being in this database is AT LEAST 35%.
Note 2 - Only 1/2 of Co. Cork's rcds are in this database.
Note 3 - The RC church kept control over most parish rcds from Tipperary (north). These are ONLY available thru the Tipperary Family History Research center at a substantial fee (regardless of outcome).
For John Leahy B 1812 +/- 4 yrs, I found 25 B rcds: 2-1808 Cork, 1808 Limerick, 1808 Clare, 1810 Limerick, 3-1810 Cork, 2-1811 Tipperary, 2-1811 Cork, 4-1813 Cork, 1814 Limerick, 2-1814 Cork, 1814 Westmeath, 1815 Limerick, and 3-1816 Cork.
For Mary Harrington M 1836 (exact), I found 2 M rcds: Cork and Tipperary.
For John Leahy M 1836 ditto, I found 3 M rcds: 2-Limerick and Cork.
It seems the ones in Cork are for your ancestors. A vew of the M rcds will show if the M was to each other. It also SHOULD show their parents' names, residences, etc. The fathers' names will help validate their B rcds.
Google the Foundation's name to lead you to this database. Register, opt to be notified as rcds are added and browse. Pls post your search results to my genforum msg.