If they were married in Canada, there is a good chance that their marriage record will have their parents' names and maybe even their county of origin in Ireland. The church records (Drouin Collection) is where to look. I'm pretty sure they are at familysearch, I know they are at ancestry.com, and good genealogy libraries will have them on film. One catch: a lot of them are in French. But most of it is "boilerplate", standardized phrasing, and the names are easy to pick out. Use Google translate for the dates, etc.
As usual, always work backward from what you know, and look everywhere: every child's birth, etc.. And look for siblings of Patrick and Julia also. If you find the siblings' parents, you find the parents!