There are no really good etymological dictionaries for Gaelic, and MacBain and Wiktionary give us no information.
I think we can all accept that the co- is the same as it is clearly something we do together.
The best I can do for coinnich/coinneachadh is 'hospitality' as one meaning of inneach although this is a bit obscure and is not mentioned in Dwelly or Mark.
Another possibility is inneas 'report'.
Neither of these is too convincing, so that leaves as a possibility it being a simple borrowing of Latin cognoscĕre, with the gn becoming nn.