This may not be helpful to you. I am trying to find my Coyne relations also. My great-grandfather, Michael O'Malley, married a Sarah Coyne. This was probably around 1880 or a little later. One oral tradition in my family is that they were from just across the fjiord from Leenane in County Mayo, but in another version they were from Clifden.
I have absolutely no documentary proof of this, except that Sarah Coyne's name appears on my grandfather's death certificate and marraige license.