Faits : A. A.a. C._ est née en 2014 à X._ (GE) de la relation entretenue par B._ (1976), de nationalité russe, et A._ (1972), de nationalité belge. C._ a été reconnue par son père devant l'officier d'état civil. B._ a un fils, né en 2006 de son mariage avec D._, désormais dissous. A.b. Le 5 mai 2015, B._ et A._ ont signé une déclaration concernant l'autorité parentale conjointe, laquelle a été ratifiée par le Tribunal de protection de l'adulte et de l'enfant (ci-après: le Tribunal de protection) le 18 mai 2015. B. B.a. Le 12 décembre 2016, B._ a formé devant le Tribunal de protection une requête en constatation de l'autorité parentale exclusive de la mère non mariée, assortie d'une requête de mesures superprovisionnelles et provisionnelles. A ce dernier titre, B._ a conclu à ce que tout contact entre C._ et A._ fût interdit pour une durée indéterminée, mais dans tous les cas jusqu'à la fin de la procédure pénale ouverte à l'encontre de E._, ami de A._, pour actes d'ordre sexuel avec des enfants, à ce qu'il fût fait interdiction à A._, dans tous les cas, de sortir du territoire suisse avec l'enfant C._, à ce qu'il fût constaté que l'autorité parentale exclusive (y compris le droit de garde exclusif), était détenue par la mère et au besoin à ce que cette autorité parentale exclusive lui fût attribuée. Sur le fond, B._ a conclu à ce que la déclaration concernant l'autorité parentale conjointe du 5 mai 2015 fût invalidée pour vice de forme, à ce qu'il fût constaté qu'elle était toujours seule titulaire de l'autorité parentale sur l'enfant C._, à ce qu'un droit de visite fût attribué à A._ avec interdiction de quitter le territoire suisse et à condition qu'il fût libéré de toutes charges à l'issue de la procédure pénale ouverte à l'encontre de E._. Subsidiairement, et si le Tribunal de protection devait considérer qu'elle-même et A._ détenaient tous deux l'autorité parentale conjointe, à ce que celle-ci fût retirée au père pour lui être attribuée exclusivement. Par ordonnance du 13 décembre 2016 rendue sur mesures superprovisionnelles, le Tribunal de protection a fait interdiction à A._ d'entretenir des contacts avec sa fille, de modifier le lieu de résidence de la mineure et de quitter avec elle le territoire suisse, sans son autorisation préalable. Le dépôt immédiat des documents d'identité de la mineure en possession de son père a été ordonné en mains du Service de protection des mineurs (ci-après: SPMi) et l'autorité parentale sur l'enfant a été retirée au père. La décision a été prise sous la menace de la peine prévue à l'art. 292 CP et l'inscription de la mineure au RIPOL a été ordonnée. B.b. Le 14 décembre 2016, A._ a déposé à son tour une requête de mesures superprovisionnelles et provisionnelles de protection pour la mineure C._, concluant à ce qu'il fût fait interdiction à B._ de déplacer la résidence de l'enfant, à ce que celle-ci fût inscrite dans les registres de police suisses et internationaux, à ce qu'il fût ordonné à la mère de déposer les papiers d'identité de la mineure et à ce que lui-même pût bénéficier d'un droit de visite. Par ordonnance du 16 décembre 2016, le Tribunal de protection, statuant sur mesures superprovisionnelles, a fait interdiction à B._ de modifier le lieu de résidence de sa fille, de faire quitter la Suisse à l'enfant sans l'autorisation préalable du Tribunal de protection, a ordonné le dépôt immédiat des documents d'identité de la mineure en mains du SPMi, la décision étant rendue sous la menace de la peine prévue à l'art. 292 CP, et a ordonné l'inscription de l'enfant au RIPOL. B.c. Le 19 décembre 2016, le conseil de B._ a informé le Tribunal de protection que celle-ci, accompagnée de sa fille était partie pour Y._ (Russie) le 6 (recte: 16) décembre 2016 à 7h30 du matin, à savoir avant la notification de l'ordonnance rendue le même jour. Sa cliente serait toutefois de retour après les fêtes de fin d'année, à savoir le 8 janvier 2017. B.d. Le 22 décembre 2016, A._ a sollicité du Tribunal de protection qu'il revienne sur l'interdiction qui lui avait été faite d'entretenir toute relation avec sa fille et sur le retrait de l'autorité parentale. Il indiquait avoir été entendu le 13 décembre 2016 dans le cadre de la procédure pénale diligentée pour actes d'ordre sexuel à l'encontre de E._ et ne pas avoir été mis en prévention. Il contestait également le vice de forme allégué par B._ relatif à la déclaration d'autorité parentale conjointe. B.e. Le 28 décembre 2016, B._ a formé devant les tribunaux de Y._ une demande tendant à faire constater que le domicile de sa fille se trouvait en Russie; elle a également réclamé le versement d'une contribution d'entretien à A._. B.f. Le 9 janvier 2017, le conseil de A._ informait le Tribunal de protection que B._ n'était pas rentrée de Russie, contrairement à ce qu'elle avait précédemment affirmé. Par courrier de son conseil du 12 janvier 2017, B._ a fait part de son intention de rester provisoirement en Russie, déclarant craindre pour sa vie et pour l'intégrité corporelle de ses enfants. Le même jour, un second courrier a été adressé au Tribunal de protection, courrier indiquant que trois experts avaient examiné C._ en Russie. Ceux-ci étaient unanimes quant au fait que l'enfant avait " sans aucun doute " participé à des jeux à caractère sexuel et avait " très probablement " été victime d'attouchements ou autres actes à caractère sexuel. B.g. Le 25 janvier 2017, A._ s'est déterminé sur la requête de mesures provisionnelles formée par B._ devant le Tribunal de protection. Il a conclu à son rejet et, faisant suite à sa propre requête de mesures provisionnelles, à ce que l'autorité parentale conjointe sur l'enfant fût immédiatement réinstaurée, à ce qu'un droit de visite lui fût réservé, à ce qu'il fût ordonné à B._ de rapatrier immédiatement l'enfant sous la menace de la peine de l'art. 292 CP et à ce que l'interdiction faite à l'intéressée de quitter le territoire suisse fût confirmée. B.h. Par ordonnance du 6 février 2017, le Tribunal de protection, statuant sur mesures provisionnelles, a notamment levé l'interdiction faite à A._ d'entretenir tout contact avec sa fille C._, lui a restitué l'autorité parentale sur l'enfant, lui a réservé un droit aux relations personnelles devant s'exercer à raison de trois contacts téléphoniques par semaine dans l'attente du rapport d'évaluation sociale que le SPMi était invité à établir dans les meilleurs délais. B.i. Le SPMi a rendu son rapport le 11 mai 2017. Celui-ci relevait le manque de coopération de B._ dans la mise en oeuvre du droit de visite via Skype; il soulignait en revanche la collaboration du père de l'enfant et ses bonnes compétences parentales. B.j. Une requête de retour fondée sur la CLaH80 a été transmise à l'Autorité centrale russe le 16 mai 2017 par l'intermédiaire de l'Office fédéral de la justice. La médiation entre les parties a échoué. B.k. Par ordonnance du 21 novembre 2017, statuant sur mesures provisionnelles, le Tribunal de protection a notamment retiré à B._ la garde de fait et le droit de déterminer le lieu de résidence de C._, ordonné le placement de l'enfant chez son père, ordonné à B._ de ramener la mineure en Suisse et réglé le droit aux relations personnelles entre celles-ci. B._ a formé recours contre cette ordonnance, sollicitant la restitution de l'effet suspensif. Par décision du 18 décembre 2017, la Chambre de surveillance de la Cour de justice a attribué l'effet suspensif au recours; le Tribunal fédéral a déclaré irrecevable le recours formé par A._ contre cette décision (arrêt 5A_68/2018 du 23 janvier 2018). La Chambre de surveillance a annulé l'ordonnance du 21 novembre 2017 par arrêt du 5 décembre 2018, estimant que la compétence pour prendre des mesures tendant à la protection de l'enfant avait été transférée à la Russie. C. Agissant le 7 janvier 2019 par la voie du recours en matière civile au Tribunal fédéral, A._ (ci-après: le recourant) conclut à l'annulation de la décision cantonale et à sa réforme en ce sens que préalablement, il soit dit et constaté que les autorités judiciaires suisses sont compétentes pour prendre toutes mesures de protection concernant la mineure C._. A titre principal, le recourant demande que la garde de fait et le droit de déterminer le lieu de résidence de l'enfant soient retirés à B._ (ci-après: l'intimée), que le placement de l'enfant soit ordonné chez lui, qu'il soit ordonné à l'intimée de ramener l'enfant en Suisse et de collaborer avec les curateurs, un droit aux relations personnelles à raison d'un week-end sur deux, d'une journée en semaine et la moitié des vacances scolaires avec interdiction de quitter la Suisse étant réservé à l'intimée, qu'une curatelle d'organisation et de surveillance des relations personnelles entre la mineure et l'intimée soit instaurée, qu'une curatelle d'assistance éducative soit mise en place, le SPMi étant invité dans les plus brefs délais à transmettre le nom des intervenants désignés à ce titre et les mesures prises dans les ordonnances des 13 et 16 décembre 2016 étant maintenues pour le surplus; à titre subsidiaire, le recourant sollicite le renvoi de la cause à l'instance cantonale pour nouvelle décision au sens des considérants. L'intimée a spontanément produit devant la Cour de céans copie de l'ordonnance rendue le 20 novembre 2018 par la Cour suprême de la Fédération de Russie, décision rejetant le pourvoi en cassation formé par le recourant dans le cadre de sa requête en retour de l'enfant. Invités à se déterminer, l'intimée a conclu au rejet du recours, la cour cantonale s'est référée aux considérants de son arrêt et le SPMi n'a présenté aucune observation. Les parties n'ont pas déposé d'écritures complémentaires.