Lyn,
Molloy would be a native Irish name, and so probably was Agnew (some sources say it is a Norman name). So I would expect them to have both been Catholic. But I wanted to check.
Marriages were entered into the statutory records in Ireland from 1845 onwards, save for Catholic marriages, which were not included until 1864. This couple told the Registrar in Dundee that they married in Co Derry in 1860. I have searched the statutory records and can’t see that marriage which points to it being Catholic (or to them not actually having married at all, and just made a date up).
RC marriage records are mostly on-line on various sites (Ancestry, fmp and the National Library, Dublin) but not every parish has records for the 1860s and some have been lost or overlooked when they were filmed. As an example, the RC parish of Dungiven in Co. Derry has marriage records starting in 1825 but there’s a gap from 1834 to 1864, so if your couple married there, you won’t find any record). I searched the set on Ancestry and did not find the marriage, anywhere in Ireland.
I would check the Scottish censuses in case the couple put an exact place of birth in. Usually they just put Ireland but you do sometimes see a parish or a townland.
The only other thing I can think of is focussing on the surname Payne. It is not a common name in Co. Derry. In the 1831 census there were only about 6 families in the county. You might want to search the relevant RC parish records on the NLI site in case you find the marriage and it has been overlooked or mis-spelled in other sources. With a specific date to check, going through 6 or 7 sets of records should not take too long. And if a likely parish has a gap in its marriage records around 1860 that could be a clue. The 1831 Co. Derry census lists Payne households in the civil parishes of Drumachose, Tamlaghtard, Desertmartin, Kilcronaghan & Templemore. Folk tended to marry locally so you would hope that the Agnew family lived nearby, ideally in the same parish. The 1831 census has Agnew families in Drumachose & Desertmartin, so they might be worth checking first.
Possibly DNA testing may be a way of matching with others who have additional information about where the family originate. Family Tree DNA reportedly has more people with Ulster roots than any other company. That obviously increases the chances of finding a match. You might want to try them or, if you have already tested, you can transfer your results for no fee.
The North of Ireland Family History Society is running an Ulster DNA project and can offer FTDNA testing kits at a reduced price. http://www.nifhs.org (Go to DNA project on the website).