Faits: A. A._, employée dans le secteur du commerce de détail et membre du syndicat X._, a été engagée par Y._ & Cie (ci-après: Y._) tout d'abord en qualité de collaboratrice de vente temporaire du 18 novembre au 24 décembre 2005, puis comme collaboratrice fixe dès le 1er mars 2006. Par courrier du 18 février 2009, Y._ a licencié A._ pour le 30 avril 2009. La lettre de licenciement reproche pour l'essentiel à l'employée une interview qu'elle a donnée à W._ le 24 décembre 2008, dans laquelle elle critique la pratique de l'entreprise (sans la citer) en relation avec l'ouverture nocturne des magasins. Le syndicat X._ a contesté ce licenciement, soutenant qu'il intervenait en raison des activités syndicales de A._, qui était représentante des travailleurs au sein de la Commission O._. Estimant qu'un tel congé frappe non seulement le travailleur, mais le syndicat lui-même, X._ a fait valoir qu'un tel licenciement était interdit par l'art. 17 al. 2 de la Convention cadre du commerce de détail (ci-après: CCT), dont X._ et Y._ sont signataires. L'art. 17 al. 2 CCT prévoit qu'il est interdit de discriminer ou de licencier un employé en raison de son activité exercée en qualité de représentant, de délégué syndical ou de membre des commissions du personnel des employés. La procédure devant la Commission paritaire professionnelle du commerce de détail a été paralysée en raison d'une divergence complète entre les parties. B. B.a Le 30 avril 2009, le syndicat X._ a déposé une requête dirigée contre Y._ auprès de la Chambre des relations collectives de travail, concluant, à titre de mesures provisionnelles, à ce que A._ soit réengagée provisoirement à partir du 1er mai 2009 et, sur le fond, à ce que le licenciement soit annulé et à ce que l'employée réintègre son poste à partir du 1er mai 2009. Y._ a conclu, sur les mesures provisionnelles, à ce que la requête soit déclarée irrecevable, subsidiairement à ce qu'elle soit rejetée; sur le fond, Y._ conclut à l'irrecevabilité de la demande, à son rejet, ainsi qu'à la condamnation du syndicat à une amende et à une peine conventionnelle pour avoir violé ses obligations légales et conventionnelles en lien avec l'obligation de maintenir la paix du travail. Par décision du 26 mai 2009, intitulée "décision sur mesures provisionnelles", la Chambre des relations collectives de travail a déclaré la demande recevable et ordonné la réintégration de A._ jusqu'à droit jugé sur le fond. Le recours en matière civile interjeté au Tribunal fédéral par Y._ contre cette décision a été déclaré irrecevable, par arrêt du 30 septembre 2009. B.b Par décision du 16 mars 2010, la Chambre des relations collectives de travail a statué sur le fond de la cause. Elle a déclaré la demande déposée le 30 avril 2009 par le syndicat X._ irrecevable; elle a débouté Y._ de ses conclusions reconventionnelles, ainsi que les parties de toute autre conclusion. C. Le syndicat X._ exerce un recours en matière civile au Tribunal fédéral contre cette dernière décision. Il conclut, sous suite de frais et dépens, à l'annulation de la décision attaquée et à ce qu'il soit ordonné à Y._, sous la menace de la peine d'une amende prévue par l'art. 292 CP dirigée contre ses associés, d'annuler le licenciement de A._, de la réintégrer à son poste à partir du 1er mai 2009 et de débouter Y._ de toutes autres ou contraires conclusions. Subsidiairement, il conclut, sous suite de frais et dépens, à l'annulation de la décision attaquée, à ce qu'il soit dit que le syndicat X._ a la qualité pour agir contre Y._ et que les conclusions de sa demande sont recevables, au renvoi de la cause à la Chambre des relations collectives de travail pour nouvelle décision et au déboutement de Y._ de toutes autres ou contraires conclusions. Y._ a conclu au rejet du recours dans la mesure où il est recevable, avec suite de frais et dépens. La requête d'effet suspensif présentée par le recourant a été écartée par ordonnance présidentielle du 27 mai 2010.