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.
For Martin Concannon B 1836 +/- 4 yrs in Co. Mayo to a father named Pat(rick), I found 0 B rcds.
For Julia Walsh B 1840 in Co. Mayo, I found 3 B rcds: 1- 1839, 2-1841. One of these MAY be for your ancestor.
For a Patrick Concannon B 1863 (exact) in Co. Mayo with a father named Martin, I found 1 B rcd. This fits your info exactly. The rcd is likely for your ancestor. A view of the detailed rcd MAY show that the mother was named Julia. If so, this would validate the rcd.
For a Martin & Julia marriage in 1862 +/- 1 yr in Co. Mayo, I found 1 M rcd for Martin in 1862, but no corresponding M rcd for Julia. I have found cases where the IFHF transcribers digitized data for one marriage partner, but not the other. This may be another.
Google the Foundation's name to lead you to this database. Pls post your results to my genforum msg.