My grandmother was a McNulty who grew up in East Mayo, so I can add a bit more info to what Roger told you.
In Irish, the surname McNulty is Mac an Ultaigh, which literally means “son of the Ulsterman” (Ultach = Ulsterman, and Ultaigh is the genitive case of the word), but it may simply refer to descent from the Ulaid, a people for whom Ulster is named (in ancient Ireland, the Uluti tribe), which in remote times ruled the entirety of the North of Ireland. According to MacLysaght’s “Surnames of Ireland”, the McNulty surname originated in County Donegal, and that is where the Mayo McNulty’s came from.
A family of McNulty's migrated to the Callow Lakes area in eastern Mayo in the 1640's, according to a history of the parish of Killasser (where Callow is located). In the course of time, McNulty’s became numerous in East Mayo. There are still McNulty’s in Donegal and nearby counties, and McNulty emigrants from Ulster are also known to have moved to Counties Louth and Meath (in Meath, they usually just use the name Nulty, however). As it happens, my great-great-grandfather was named James McNulty, but he was born around 1800, so would be too old to be the same person as your James. He had a son named Thomas (probably Tadhg), my great-grandfather, but I don't know the names of his other children.
As Roger noted, there are O'Connor's all over Ireland (there were, in fact, originally six separate "clans" of them). There was a "clan" which originated in Connacht, I think originally in Sligo, so that might be the family of your Mary, since the parish of Killasser is right on the Mayo-Sligo border. Of course, if they only met once they were in the US, she could have come from somewhere else in Ireland.