Since you have their address you may be able to determine what church they attended. Were they Catholic? Some church records are available on microfilm through the LDS library. Other records are still held by the parish or diocese. Church records will have marriage, births/baptisms, and more important for you - deaths and burials. If your ancestor did die in New York he may have had a church funeral.

Do you know where Margaret is buried and did you check with that cemetery for her husband? Have you contacted the New York City vital records for a death record for Patrick Connell?