Citation: 5A_712/2022 E. C

Par acte du 16 septembre 2022, A.________ forme un recours en matière civile contre cette décision. Il conclut principalement à son annulation et à sa réforme en ce sens qu'il est dit que le Tribunal de protection est compétent pour connaître de la cause relative à la mineure et pour prendre toutes décisions en matière de relations personnelles et mesures de protection vis-à-vis d'elle, que la cause est renvoyée au Tribunal de protection pour suite d'instruction et prise de décision au fond et qu'il est ordonné aux autorités judiciaires valaisannes de transmettre le dossier de la cause au Tribunal de protection. Subsidiairement, il conclut à l'annulation de la décision querellée, au renvoi de la cause à la Cour de justice pour nouvelle décision dans le sens des considérants et à ce qu'il soit ordonné aux autorités judiciaires valaisannes de transmettre le dossier de la cause au Tribunal de protection. Invitées à se déterminer, la Cour de justice s'est référée aux considérants de son arrêt et l'intimée a conclu au rejet du recours. Les parties ont répliqué et dupliqué.