Sachverhalt:
A.
X._ (1966) und Z._ (1970) haben die gemeinsamen Kinder S._ (2005) und T._ (2007). Mit Urteil des Gerichtshofes der persönlichen Fälle der Nicht-Muslime in Dubai (Vereinigte Arabische Emirate, VAE) vom 11. Januar 2010 wurde die Ehe zwischen den Parteien geschieden. S._ hält sich bei der Mutter in Zürich auf, T._ beim Vater in Dubai bzw. Abu Dhabi.
B.
Am 4. Januar 2013 stellte der Vater ein Gesuch um Rückführung der Tochter S._ nach Griechenland, innert fünf Tagen ab Rechtskraft des Entscheides und unter Androhung der Ungehorsamsstrafe. Ferner verlangte er, der Mutter für die Dauer des Verfahrens zu verbieten, das Kind ausser Landes zu bringen, und es seien die Parteien zu verpflichten, im Rahmen einer Mediation die freiwillige Rückkehr des Kindes oder eine gütliche Regelung zu bewirken.
Mit Entscheid vom 14. Februar 2013 trat das Obergericht des Kantons Zürich auf das Gesuch nicht ein mit der Begründung, der gewöhnliche Aufenthalt von S._ in Griechenland vor der behaupteten Entführung in die Schweiz sei nicht (genügend) nachgewiesen und die VAE, wo die Parteien vorher gelebt hätten und der gesuchstellende Vater sein Domizil verzeige, seien nicht Vertragsstaat des Haager Rückführungsübereinkommens.
C.
Gegen diesen Entscheid hat der Vater am 28. Februar 2013 eine Beschwerde in Zivilsachen und eine subsidiäre Verfassungsbeschwerde eingereicht mit den Begehren, die Parteien seien zu verpflichten, im Rahmen einer Mediation eine freiwillige Rückführung des Kindes zu erreichen oder eine gütliche Regelung der Angelegenheit herbeizuführen, eventualiter sei auf das Rückführungsgesuch einzutreten und die Sache zur materiellen Beurteilung an das Obergericht zurückzuweisen, subeventualiter sei das Verfahren zur Neubeurteilung an die Vorinstanz zurückzuweisen. Mit Vernehmlassung vom 11. März 2013 hat die Beschwerdegegnerin auf Abweisung der Beschwerde geschlossen, soweit darauf einzutreten sei. Sie hat ferner ein Gesuch um unentgeltliche Rechtspflege gestellt. Am 17. April 2013 hat der Beschwerdeführer privat eine E-Mail mit Beilagen gesandt.
D.
Das Bundesgericht hat das Urteil am 18. April 2013 öffentlich beraten.

Erwägungen:
1.
Bei Rückführungsentscheiden nach dem Haager Übereinkommen über die zivilrechtlichen Aspekte internationaler Kindesentführung (HKÜ, SR 0.211.230.02) geht es um die Regelung der Rechtshilfe zwischen den Vertragsstaaten (<ref-ruling> E. 2b S. 224), die in unmittelbarem Zusammenhang mit der Respektierung und Durchsetzung ausländischen Zivilrechts steht (Art. 72 Abs. 2 lit. b Ziff. 1 BGG; <ref-ruling>). Gegen den Entscheid des Obergerichtes des Kantons Zürich, welches als einzige kantonale Instanz entschieden hat (Art. 7 Abs. 1 des Bundesgesetzes über internationale Kindesentführung und die Haager Übereinkommen zum Schutz von Kindern und Erwachsenen, BG-KKE, SR 211.222.32), steht deshalb die Beschwerde in Zivilsachen grundsätzlich offen. Wo die Beschwerde in Zivilsachen offen steht, ist die subsidiäre Verfassungsbeschwerde - wie es schon ihr Name sagt - ausgeschlossen (vgl. <ref-law>).
Was die beiden mit E-Mail vom 17. April 2013 zugesandten Dokumente anbelangt, so sind elektronische Eingaben grundsätzlich nur zulässig, wenn die dafür vorgesehene Plattform verwendet wurde, was vorliegend nicht der Fall ist. Das eine Dokument ist ein (undatiertes) Zeugnis der A._ School, welches ohnehin erst nach Ablauf der Beschwerdefrist, mithin verspätet eingereicht wurde und darüber hinaus ein unzulässiges Novum im Sinn von <ref-law> wäre. Das zweite Dokument ist eine Stellungnahme des griechischen Anwaltes des Beschwerdeführers, in welchem der Sachverhalt aus dessen Sicht geschildert wird. Soweit das Schreiben dem Beschwerdeführer zugerechnet wird, könnte es als Ausübung des Replikrechts angesehen werden. Inhaltlich enthält es freilich keine neuen Gesichtspunkte.
2.
Der Beschwerdeführer rügt, dass im kantonalen Verfahren keine persönliche Anhörung stattgefunden hat.
2.1. Der Vorwurf an das Obergericht, ihn nicht persönlich angehört zu haben, erscheint insofern etwas befremdend, als der Beschwerdeführer im parallelen Abänderungsverfahren gegenüber dem Bezirksgericht vorgebracht hat, er könne die von ihm betreute T._ nicht tagelang allein in den Emiraten zurücklassen, weshalb er die Dispensation von der anberaumten Verhandlung verlange. Es lässt sich aber nicht gerade von Rechtsmissbrauch bzw. treuwidrigem prozessualem Verhalten sprechen, wenn der Beschwerdeführer im vorliegenden Rückführungsverfahren eine unterbliebene persönliche Anhörung moniert.
2.2. Konkret macht der Beschwerdeführer geltend, er habe die Parteibefragung als Beweismittel angeboten und es sei willkürlich, wenn das Obergericht dieses nicht abgenommen, sondern aufgrund der Akten entschieden habe.
Soweit ein Gericht zum Schluss kommt, dass weitere Beweisvorkehren an der Würdigung der bereits abgenommenen Beweise voraussichtlich nichts mehr ändern würden, darf es in zulässiger antizipierter Beweiswürdigung auf weitere Abklärungen verzichten (<ref-ruling> E. 2.1 S. 429). Der Beschwerdeführer zeigt entgegen den Substanziierungsanforderungen an Willkürrügen (dazu <ref-ruling> E. 2.2 S. 246) nicht auf, inwiefern seine Einvernahme neue Erkenntnisse hätte erwarten lassen und die vorinstanzliche Beweiswürdigung im Zusammenhang mit dem gewöhnlichen Aufenthalt von S._ (dazu E. 3) entscheidend hätte beeinflussen oder gar ändern können.
Eine Verletzung des Willkürverbotes im Zusammenhang mit der persönlichen Anhörung ist nach dem Gesagten nicht dargetan.
2.3. Eine Verletzung des rechtlichen Gehörs (<ref-law>) macht der Beschwerdeführer im vorliegenden Kontext nicht geltend. Ohnehin gäbe der verfassungsmässige Anspruch gemäss <ref-law> kein Recht auf mündliche Anhörung (<ref-ruling> E. 9b S. 219; <ref-ruling> E. 5.3 S. 148) und wäre überdies von vornherein keine Gehörsverletzung gegeben, wo ein Gericht in willkürfreier antizipierter Beweiswürdigung auf eine mündliche Anhörung verzichtet hat (<ref-ruling> E. 3 S. 157).
2.4. Sodann wird auch keine Gesetzesnorm als verletzt angerufen. Zwar wendet das Bundesgericht das Recht von Amtes wegen an (<ref-law>). Indes ist es nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu prüfen, wenn diese nicht oder nicht mehr vorgetragen werden (134 III 102 E. 1.1 S. 105; <ref-ruling> E. 1.4 S. 400). <ref-law> verlangt vielmehr, dass in der Beschwerdebegründung in gedrängter Form darzulegen ist, inwiefern der angefochtene Akt Recht verletzt. Es ist deshalb unerlässlich, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Verletzung von Bundesrecht liegt (Urteile 4A_744/2011 vom 12. Juli 2012 E. 2.1; 4A_709/2011 vom 31. Mai 2012 E. 1.3).
3.
Vorliegend stellt sich die Frage des Anwendungsbereiches des HKÜ und damit zusammenhängend die Frage, ob das Kind S._ unmittelbar vor dem Verbringen in die Schweiz am 9. Januar 2012 in Griechenland seinen gewöhnlichen Aufenthalt hatte (vgl. Art. 3 Abs. 1 lit. a und Art. 4 HKÜ).
Der Begriff des gewöhnlichen Aufenthaltes im Sinne des HKÜ ist vertragsautonom auszulegen und entspricht dem Anknüpfungsbegriff, wie er im Minderjährigenschutzabkommen (MSA; SR 0.211.231.01) und in anderen Haager Übereinkommen verwendet wird (Urteil 5P.367/2005 vom 15. November 2005 E. 5.1). Allgemein wird er bestimmt durch den tatsächlichen Mittelpunkt der Lebensführung des Kindes (vgl. <ref-ruling> E. 3 S. 122; <ref-ruling> E. 4a S. 337), wobei auf die nach aussen erkennbaren Umstände abzustellen ist und es auf subjektive Momente nicht ankommt (BGE <ref-ruling> E. 4a S. 337; <ref-ruling> E. 4.1 S. 292). Vorausgesetzt ist eine gewisse tatsächliche Dauer des Aufenthaltes sowie eine damit zusammenhängende gewisse Integration im familiären und sozialen Umfeld, wobei auch andere Faktoren wie Nationalität, Sprachkenntnisse und Einschulung eine Rolle spielen können (Urteil 5A_889/2011 vom 23. April 2012 E. 4.1). In der Regel fällt der gewöhnliche Aufenthalt mit dem Lebensmittelpunkt mindestens eines Elternteils zusammen (dazu BGE <ref-ruling> E. 4.1 S. 292).
Bei der Feststellung des Aufenthaltsortes des Kindes kann in der Regel kein klarer Beweis geführt werden, sondern ist aufgrund von Indizien eine Gewichtung der vorgenannten relevanten Umstände vorzunehmen. Die gerichtliche Würdigung dieser Indizien und die sich daraus ergebenden tatsächlichen Schlussfolgerungen sind Tatfragen. Daher ist die auf eine Würdigung konkreter Umstände gestützte Beurteilung des Aufenthaltsortes des Kindes im Zeitpunkt der behaupteten Entführung für das Bundesgericht verbindlich (<ref-law>), ausser wenn sie "offensichtlich unrichtig" im Sinn von <ref-law> ist, wobei dieser Begriff mit "willkürlich" gleichzusetzen ist (Botschaft, BBl 2001 IV 4338; <ref-ruling> E. 1.2.2 S. 252; <ref-ruling> E. 7.1 S. 398). Hierfür gilt das strenge Rügeprinzip (<ref-law>).
Gemäss Version der Beschwerdegegnerin weilte das Kind S._ lediglich wenige Tage ferienhalber in Griechenland, bevor sie mit ihm am 9. Januar 2012 in die Schweiz reiste. Demgegenüber behauptet der Beschwerdeführer, die Familie habe im Sommer 2011 definitiv in Piräus Wohnsitz genommen, wo sie bereits seit zwei Jahren angemeldet gewesen sei, und S._ habe dort die Schule besucht. Das Obergericht ist aufgrund einer detaillierten Beweiswürdigung zum Schluss gekommen, der Nachweis, wonach S._ unmittelbar vor dem Verbringen in die Schweiz ihren gewöhnlichen Aufenthalt in Griechenland gehabt hätte, sei nicht erbracht worden. Diese Beweiswürdigung (dazu E. 3.1) wird in verschiedener Hinsicht als willkürlich kritisiert (dazu E. 3.2 - 3.4).
3.1. Gemäss den im angefochtenen Entscheid festgehaltenen Aussagen geht die Darstellung des Beschwerdeführers dahin, dass die Familie im Sommer 2011 gemeinsam Wohnsitz in Piräus genommen habe; dies sei der übereinstimmende Wille der Parteien gewesen. S._ sei am 27. August 2011 in Griechenland eingereist und habe vom 1. September bis 28. Dezember 2011 in Piräus einen Englischkurs absolviert. Die Darstellung der Beschwerdegegnerin geht demgegenüber dahin, dass sie von Abu Dhabi in die Schweiz zurückkehren wollte, was der Beschwerdeführer zu verhindern gewusst habe. Sie sei gegen ihren Willen dort geblieben und er habe eine Rückkehr in die Schweiz in den Sommerferien abgelehnt. Am 1. August 2011 seien sie nach Griechenland in die Ferien gefahren. Seit September 2011 besuche T._ in Abu Dhabi einen englisch-französischen Kindergarten. S._ sei in Abu Dhabi bis zum 28. Dezember 2011 zur Schule gegangen. An diesem Tag sei sie mit S._ nach Griechenland geflogen, um dort die Nach-Weihnachtstage zu verbringen. Der Beschwerdeführer sei am 6. Januar 2012 mit T._ nach Abu Dhabi zurückgekehrt, um die Arbeit aufzunehmen. Sie sei indessen am 9. Januar 2012 mit S._ in die Schweiz geflogen, weil sie es in Abu Dhabi nicht mehr ausgehalten habe.
Das Obergericht hat sodann die vom Beschwerdeführer für den gewöhnlichen Aufenthalt von S._ in Griechenland angerufenen Beweismittel auf ihre Plausibilität hin überprüft bzw. gewürdigt. Es hat dabei befunden, dass die (ohnehin ganz allgemein gehaltene) Behauptung einer gemeinsamen Wohnsitznahme in Griechenland im Sommer 2011 angesichts der per Januar 2010 erfolgten Scheidung auffällig sei und in diametralem Widerspruch zur Schilderung der Beschwerdegegnerin anlässlich ihrer Befragung im Zusammenhang mit dem von ihr vor dem Bezirksgericht Zürich eingeleiteten Abänderungsverfahren stehe. Die vom Beschwerdeführer eingereichte Bescheinigung des Bürgermeisters von Piräus vom 22. März 2010 könne schon deshalb kein Beleg für den geltend gemachten Aufenthalt sein, weil sie lange vor dem Zeitpunkt ausgestellt worden sei, ab welchem S._ angeblich in Griechenland gewohnt haben soll. Der Beschwerdeführer gebe denn auch selber an, diese Bestätigung sei im Hinblick auf eine vorgesehene Wohnsitznahme erfolgt. Aus den gleichen Gründen belege auch die Bestätigung vom 2. März 2012 der "Municipality of Piraeus", wonach der Beschwerdeführer seit zwei oder mehr Jahren an der fraglichen Adresse in Piräus wohne, keinen Wohnsitz des Kindes, zumal die Kinder in der Bescheinigung nicht aufgeführt seien; im Übrigen figuriere die Beschwerdegegnerin als "Ehefrau", obwohl die Parteien seit Januar 2010 geschieden seien. Kein Wohnsitz des Kindes in Griechenland lasse sich sodann aus der am 27. November 2010 ausgestellten steuerlichen Registrierung in Piräus ableiten, da sie sich auf einen früheren Zeitpunkt und allein auf den Beschwerdeführer beziehe.
Das Obergericht hat weiter befunden und erwogen, gemäss Behauptung des Beschwerdeführers in der ergänzenden Eingabe vom 4. Februar 2013 sei S._ am 27. August 2011 in Griechenland eingereist. Der Reisepass von S._ belege aber gerade umgekehrt die Einreise am 27. August 2011 in die VAE. Ob der Beschwerdeführer mit dem Kind sodann am 11. September 2011 gemäss elektronischem Flugticket tatsächlich von Dubai nach Athen und am 21. Dezember 2011 von Athen nach Dubai geflogen sei, könne nicht nachvollzogen werden, da keine Boardingkarten eingereicht worden seien. Nachweislich sei aber die Beschwerdegegnerin mit S._ am 28. Dezember 2011 von Abu Dhabi nach Athen geflogen, lege sie doch hierfür die Boardingkarten vor und enthalte der Reisepass von S._ auch einen entsprechenden Eintrag. Wie auch immer es sich im Einzelnen verhalte, könne jedenfalls die Bestätigung der "B._ Schools", gemäss welcher S._ vom 1. September bis 28. Dezember 2011 Englischklassen besucht und diese in der genannten Zeitspanne erfolgreich absolviert haben soll, nicht zutreffen. Sodann falle auf, dass es sich um eine Sprachschule und nicht um eine Grundschule handle; der Besuch einer Sprachschule sei aber in aller Regel zeitlich limitiert und begründe keinen Wohnsitz. Im Übrigen habe S._ von September 2010 bis Januar 2011 in Zürich den Kindergarten besucht und sei sie im Jahre 2011 gemäss Darstellung der Beschwerdegegnerin vom Beschwerdeführer in Abu Dhabi eingeschult worden, so dass es auch unverständlich wäre, wieso das Kind in Griechenland bei einer tatsächlich erfolgten Wohnsitznahme nicht in den Kindergarten geschickt oder aber eingeschult worden wäre.
Vor dem Hintergrund der vorstehenden Ungereimtheiten und Widersprüche erachtete das Obergericht die weiteren seitens des Beschwerdeführers produzierten Unterlagen als nicht entscheidend. Es befand, die von einer/einem U._ am 12. Februar 2012 für V._ ausgestellte Bestätigung, dass der Beschwerdeführer als Finanzintermediär und wegen seines kulturellen Hintergrundes zu 70 - 80 % in Griechenland tätig sei, belege keinen gewöhnlichen Aufenthalt des Kindes zu Beginn des Jahres 2012. Nichts anderes ergebe sich aus der Bestätigung von W._, Human Ressource Dept der R._-Invest in Dubai, vom 2. Juli 2012. Der Beschwerdeführer verzeichne darin eine Adresse in Zürich; dass er in dieser Firma, für welche er seit September 2011 tätig sein soll, mit Aufgaben in Griechenland betraut (gewesen) sei, belege keinen dortigen gewöhnlichen Aufenthalt des Kindes, ebenso wenig wie der Umstand, dass der Beschwerdeführer zwischen 17. September und 10. Dezember 2011 in Griechenland ein Fahrzeug gemietet habe. Wenig glaubhaft seien angesichts der Widersprüche zum vorstehend geschilderten Ablauf sodann die eidesstattliche Erklärung der Mutter des Beschwerdeführers, wonach sich dieser mit der Familie im frühen September 2011 in Piräus fest niedergelassen habe und die ganze Familie ununterbrochen dort gewohnt haben soll, mit Ausnahme einer Woche in den VAE ungefähr Mitte Dezember 2011, wobei sie selbst täglich mit der Betreuung und Verpflegung der Grosskinder betraut gewesen sei und S._ von September 2011 bis zum Tag der Entführung Englisch in einem Englischkurs studiert habe. Gleiches gelte für die Bestätigungen von weiteren vier Personen aus dem Umfeld des Beschwerdeführers. Drei Schreiben seien praktisch identisch, wobei zwei Schreiben offenkundig aus der gleichen Feder stammten; sodann falle auf, dass H._ und I._ zwar behaupteten, sie würden gegenüber der Wohnung des Beschwerdeführers leben, sie aber eine ganz andere Adresse angeben würden. Im Übrigen seien alle Bestätigungen überaus allgemein gehalten resp. inhaltlich sehr dürftig. Insgesamt fehle es ihnen an Überzeugungskraft.
Schliesslich hat das Obergericht darauf hingewiesen, dass der Beschwerdeführer im Rückführungsgesuch zwar formell die Anschrift in Piräus angegeben, in der Begründung aber angeführt habe, sich mit der jüngeren Tochter T._ seit Januar 2012 in Abu Dhabi aufzuhalten; auch in der Stellungnahme vom 4. Februar 2013 habe er angegeben, sich beruflich in den Emiraten aufzuhalten, und im Abänderungsverfahren, welches er am 27. März 2012 vor dem Gerichtshof für persönliche Angelegenheiten der Nicht-Muslime in Dubai eingeleitet habe, sei eine dortige Adresse verzeigt. In seiner Eingabe vom 14. Juni 2012 an das Bezirksgericht Zürich habe er ausgeführt, in den VAE die Sorge über sein zweites Kind auszuüben und dieses nicht tagelang allein in den Emiraten lassen zu können, weshalb er um Dispensation von der anberaumten Verhandlung ersuche. Obwohl sich all diese Umstände erst ab Beginn des Jahres 2012 zugetragen hätten, seien sie doch gewichtige Hinweise dafür, dass der Beschwerdeführer seinen Wohnsitz immer in den VAE beibehalten habe, auch wenn er dazwischen möglicherweise für kürzere oder längere Zeit nach Griechenland gefahren sei. Die Behauptung, er bzw. die ganze Familie hätten sich im Sommer 2011 zu einer gemeinsamen Wohnsitznahme in Griechenland entschlossen, erscheine unglaubhaft und wirke konstruiert. Aufgrund einer E-Mail und einer Aktennotiz erhelle, dass der Beschwerdeführer im März 2012 bei der Zentralbehörde für Kindesentführung in Bern vorstellig geworden sei, wobei offenbar der Wohnsitz und damit die Eintretensfrage unklar gewesen sei, was ihm die Zentralstelle unmissverständlich mitgeteilt habe. Dem Beschwerdeführer sei somit klar geworden, dass der gewöhnliche Aufenthalt von S._ vor Anfang 2012 entscheidend sein würde, um eine Rückführung zu erreichen. Danach habe er Ende August 2012 über die griechische Zentralbehörde ein Rückführungsbegehren gestellt und dabei die Adresse in Piräus angegeben.
3.2. Der Beschwerdeführer macht eine offensichtlich unrichtige bzw. willkürliche Sachverhaltsfeststellung geltend und bringt diesbezüglich vor, das Obergericht habe eine ganze Reihe von eingereichten Beilagen nicht ausdrücklich gewürdigt. Dies mag zutreffen, hängt aber mit deren Irrelevanz zusammen, denn es ist nicht ersichtlich, inwiefern die betreffenden Dokumente einen gewöhnlichen Aufenthalt von S._ in Griechenland unmittelbar vor dem Verbringen in die Schweiz belegen könnten, weshalb jedenfalls im Ergebnis keine Willkür gegeben ist, wie sie für eine Gutheissung der Beschwerde erforderlich wäre (vgl. <ref-ruling> E. 3.1 S. 153; <ref-ruling> E. 5.4 S. 148).
Dies gilt für die Foto, die Schimmelbefall in einem Bad zeigt (gemäss Beschwerdeführer musste die Wohnung mit Blick auf die dortige Wohnsitznahme renoviert werden; gemäss Beschwerdegegnerin handelt es sich um das Badezimmer in der Wohnung der Grossmutter), ebenso wie für die Foto zu einer freien Mietwohnung (welche die Beschwerdegegnerin nicht zu kennen behauptet) und die Fotos, auf denen ein Zimmer bzw. Möbel mit Kindersachen ersichtlich sind (gemäss Beschwerdegegnerin handelt es sich um die Wohnung, in der gelegentlich Ferien verbracht wurden). Keine Aussagen über den gewöhnlichen Aufenthalt von S._ ergeben sich sodann aus der Nebenkostenabrechnung bzw. Stromrechnung der Wohnung in Piräus (gemäss Beschwerdeführer die Wohnung, in der die Familie zur fraglichen Zeit angeblich gewohnt hat), zumal Stromkosten auch bei einer leer stehenden, vermieteten oder zu Ferienzwecken benutzen Wohnung entstehen können. Gleiches gilt für den Kopfteil eines Schreibens des Bevölkerungsamtes der Stadt Zürich an den Beschwerdeführer mit Adresse in Piräus. Der Inhalt dieses Schreibens ist offensichtlich abgedeckt und es ist auch kein Datum ersichtlich; abgesehen davon fehlt jeglicher Hinweis auf die Kinder oder die Familie.
Sodann verweist der Beschwerdeführer auf eine eidesstattliche Erklärung von J._ auf dem philippinischen Konsulat, wonach sie zweimal wöchentlich in der Wohnung des Beschwerdeführers in Yas Island gewesen sei und bis Dezember 2011 die Familie nie gesehen habe. Die Beschwerdegegnerin hält demgegenüber fest, diese Person sei ihr völlig unbekannt und im Übrigen hätten sie nicht auf Yas Island, sondern an der bekannten Adresse von C._, Abu Dhabi, gewohnt. Wie es sich damit im Einzelnen verhält, kann offen bleiben, weil auch dieses Affidavit keine Aussage über den gewöhnlichen Aufenthalt von S._ per Anfang 2012 macht.
Der Beschwerdeführer verweist weiter auf seinen UAE-Gate-Pass und behauptet, mit diesem sei er zur Ein- und Ausreise ohne Pass und Stempel berechtigt, wobei er ohne Formalitäten auch Kinder mitführen dürfe (was die Beschwerdegegnerin bestreitet). So sei z.B. eine Reise von Griechenland nach Abu Dhabi ohne Pass und Stempel im August 2011 erfolgt, um alles für den Umzug nach Griechenland zu packen. In diesem Zusammenhang zeigt der Beschwerdeführer aber nicht auf, dass und inwiefern er bereits im kantonalen Verfahren behauptet hätte, er dürfe mit diesem Gate-Pass auch Kinder ohne Pass bzw. Passeintrag mitnehmen; es ist nicht Aufgabe des Bundesgerichtes in den Akten nach entsprechenden Vorbringen zu forschen (<ref-ruling> E. 6.2 S. 288). Die Behauptung muss deshalb als neu und damit unzulässig gelten (<ref-law>). Ohnehin würde sie sich schlecht mit der Tatsache vertragen, dass im Reisepass von S._ tatsächlich gestempelte Einträge ersichtlich sind, einfach nicht für die vom Beschwerdeführer im kantonalen Verfahren behaupteten Daten. Eine willkürliche (unterlassene) Beweiswürdigung durch das Obergericht ist jedenfalls nicht mit der genügenden Substanziierung dargetan (zu den Anforderungen an die Begründung von Willkürrügen vgl. <ref-ruling> E. 2.2 S. 246).
3.3. Was der Beschwerdeführer sodann zu den Beweismitteln anführt, welche das Obergericht einer tatsächlichen Würdigung unterzogen hat, besteht weitestgehend in einer Schilderung der Dinge aus eigener Sicht; solche appellatorischen Ausführungen sind aber zur Begründung von Willkürrügen ungeeignet (<ref-ruling> E. 3.1 S. 399; <ref-ruling> E. 2.2 S. 246). Willkür bei der Beweiswürdigung liegt im Übrigen nicht schon dann vor, wenn eine andere Lösung oder Würdigung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre (<ref-ruling> E. 2.2.2 S. 319). Vielmehr setzt sie spezifisch voraus, dass das Sachgericht den Sinn und die Tragweite eines Beweismittels offensichtlich nicht erkannt, ohne vernünftigen Grund ein entscheidendes Beweismittel ausser Acht gelassen oder aus den vorhandenen Beweismitteln einen unhaltbaren Schluss gezogen hat (<ref-ruling> E. 2.1 S. 9).
Appellatorisch sind insbesondere die Ausführungen des Beschwerdeführers zum angeblichen Willen der Parteien, auch nach der Scheidung einen gemeinsamen Wohnsitz zu haben, was in der Schweiz wegen seiner beruflichen Tätigkeit nicht möglich und wozu die Beschwerdegegnerin in Abu Dhabi nicht mehr gewillt gewesen sei, weshalb er ihr eben angeboten habe, nach Griechenland zu übersiedeln, sowie die Behauptung, infolgedessen könne die Familie in der zweiten Jahreshälfte 2011 offensichtlich weder in Abu Dhabi noch in der Schweiz, sondern einzig in Griechenland gelebt haben. Keine Willkür ist sodann darzutun mit der Behauptung, die Bescheinigung des Bürgermeisters von Piräus und die Bestätigung der "Municipality of Piraeus" würden gerade zeigen, dass die Familie dort habe Wohnsitz nehmen wollen. Nachzuweisen war keine allfällige familiäre Absicht, sondern nach der in E. 2 erwähnten Definition und den zutreffenden Erwägungen der Vorinstanz vielmehr der tatsächliche Aufenthalt des Kindes von einer bestimmten Dauer; in diesem Zusammenhang ist keine willkürliche Beweiswürdigung (offensichtliches Verkennen der Tragweite eines Beweismittels; offensichtlich unhaltbare Schlussfolgerung aus einem Beweismittel) ersichtlich. Aus dem gleichen Grund ist mit der Kritik an der vorinstanzlichen Beweiswürdigung mit Bezug auf die Arbeitsbestätigungen (V._ und R._-Invest) keine Willkür darzutun, zumal der Beschwerdeführer in diesem Zusammenhang lediglich von einer geplanten Wohnsitznahme in Griechenland spricht, wobei die Finanzkrise in Griechenland und die Auswirkungen des Arabischen Frühlings seine Arbeitgeber immer wieder zu kurzfristigen Änderungen der internationalen Anstellungsbedingungen veranlasst hätten. Auch mit der Anschlussbehauptung, es habe für die Familie auf der Hand gelegen, den Lebensmittelpunkt dort zu wählen, wo bereits eine Wohnung bestanden habe, ist keine Willkür darzutun mit Bezug auf die vorinstanzliche Kernerwägung, der gewöhnliche Aufenthalt von S._ in Griechenland sei nicht nachgewiesen. Soweit eine Beweiswürdigung willkürfrei ist, liegt in ihr keine Verletzung des Anspruchs auf rechtliches Gehör (<ref-ruling> E. 3 S. 157), weshalb die im Zusammenhang mit den beiden vorerwähnten Arbeitsbestätigungen erhobene Gehörsrüge unbegründet ist.
Im Zusammenhang mit der vorinstanzlichen Würdigung der Bestätigung der "B._ Schools", wonach S._ vom 1. September bis 28. Dezember 2011 einen Englischkurs besucht haben soll, was nicht mit den Einträgen im Reisepass übereinstimmt, ist keine Willkür darzutun mit dem Vorbringen, Schulbestätigungen seien erfahrungsgemäss nicht tagesgenau und würden auch Ferienabwesenheiten nicht umfassen; die Bestätigung wirft offensichtlich Fragezeichen auf und dies durfte das Obergericht in die Gesamtwürdigung einbeziehen. Ferner ist nicht ersichtlich, inwiefern die obergerichtliche Erwägung, es sei wenig nachvollziehbar, wieso S._, die in der Schweiz schon in den Kindergarten und in Abu Dhabi zur Schule gegangen sei, in Griechenland nicht eingeschult, sondern in einen Englischkurs geschickt worden sei, "absolut aktenwidrig" sein soll, zumal der Beschwerdeführer selbst darauf hinweist, dass S._ gemäss Bestätigung des Bürgermeisters von Piräus die öffentliche Schule hätte besuchen können (Beschwerde S. 10). Einzig mit dem Verweis auf das Alter des Kindes ist jedenfalls keine Willkür mit Bezug auf die Zweifel des Obergerichtes an der Bestätigung betreffend Englischkurse dargetan.
Nichts zu ändern vermag die Bestätigung der Grossmutter; das Obergericht hat die Bestätigung keineswegs übersehen, sondern im Gesamtkontext gewürdigt und berücksichtigt, dass es sich um die Mutter des Beschwerdeführers handelt. Willkür ist in diesem Zusammenhang nicht ersichtlich. Gleiches gilt für die Kreditkartenabrechnungen (die Beschwerdegegnerin behauptet, die American Express-Karte sei abgelaufen, was sich aus der vorinstanzlich eingereichten Kopie mit dem Enddatum 09/10 ergebe, und die Karte bei der Millennium Bank habe sie in den letzten drei Jahren selbst nie mehr benutzt), aus welchen sich nach den Feststellungen des Obergerichts mehrere Einkäufe der Beschwerdegegnerin in Griechenland ergeben, welche primär in den letzten August- und den ersten Septembertagen 2011 stattfanden. Die Erwägung des Obergerichtes, dies decke sich mit der Aussage der Beschwerdegegnerin, während der betreffenden Zeit Urlaub in Griechenland verbracht zu haben, erscheint nicht willkürlich. Jedenfalls ergibt sich angesichts der auf eine kurze Zeitspanne konzentrierten Belastungen nicht, dass die Familie in der ganzen zweiten Jahreshälfte 2011 in Griechenland gelebt hätte, wie der Beschwerdeführer behauptet. Ebenfalls keine Willkür ergibt sich aus dem Umstand, dass das Obergericht keinen gewöhnlichen Aufenthalt aus der Bestätigung abgeleitet hat, wonach S._ am 18. und 25. November sowie am 9. und 16. Dezember 2011 eine Snowboardschule besucht haben soll (was die Beschwerdegegnerin bestreitet). Was schliesslich die allgemeinen Bestätigungen von vier weiteren Personen anbelangt, setzt sich der Beschwerdeführer nicht mit der obergerichtlichen Erwägung auseinander, wonach drei Schreiben praktisch identisch seien bzw. zwei Schreiben offenkundig aus der gleichen Feder stammten und wonach zwei Personen behauptet hätten, in einer gegenüberliegenden Wohnung zu leben, sie aber eine ganz andere Adresse angegeben hätten. Die Willkürrüge bleibt deshalb unsubstanziiert.
3.4. Insgesamt ergibt sich, dass der Beschwerdeführer keine Willkür mit Bezug auf die vorinstanzliche Beweiswürdigung, ein gewöhnlicher Aufenthalt von S._ in Griechenland vor dem Verbringen in die Schweiz sei nicht nachgewiesen, darzutun vermag. Ergänzend sei festgehalten, dass er zwar eine Vielzahl von gemäss vorinstanzlicher Würdigung höchst zweifelhaften und teilweise tatsachenwidrigen Bestätigungen vorgelegt hat, aber gerade keine Aufenthaltsbestätigung für das Kind selbst, obwohl es bei tatsächlicher Niederlassung in Griechenland nach allgemeiner Lebenserfahrung eine solche geben müsste. Ferner sei ergänzend zur vorinstanzlichen Beweiswürdigung festgehalten, dass es bei effektiver Niederlassung der Familie in Griechenland im Sommer 2011, wie der Beschwerdeführer dies behauptet, wenig einsichtig wäre, wieso er am 6. Januar 2012 (also drei Tage vor dem Flug von Beschwerdegegnerin und S._ in die Schweiz) mit der jüngeren Tochter nach Abu Dhabi zurückgereist wäre, um dort wiederum seine Arbeit aufzunehmen. In diesem Zusammenhang durfte das Obergericht schliesslich in die Gesamtwürdigung betreffend die Glaubhaftigkeit der Darstellung durch den Beschwerdeführer miteinbeziehen, dass sich dieser mit der jüngeren Tochter auch seither in den VAE aufhält. Das Vorbringen, ohne Beschwerdegegnerin und S._ sei es ihm nicht möglich gewesen, den ursprünglichen Plan einer Wohnsitznahme in Griechenland weiterzuverfolgen, ist nicht schlüssig und jedenfalls nicht zur Begründung einer Willkürrüge geeignet, weil sich die Beschwerdegegnerin und S._ ja auch nicht in Abu Dhabi aufhalten und deshalb so oder anders kein gemeinsames Familienleben stattfindet. Wie es sich mit all diesen Elementen im Einzelnen verhält, ist aber nicht ausschlaggebend, denn Willkür liegt nach dem Gesagten nicht schon vor, wenn eine andere Möglichkeit ebenfalls gegeben oder sogar wahrscheinlicher sein könnte (vgl. E. 2.2). Nichts hilft vorliegend darüber hinweg, dass eine Kette von Ungereimtheiten besteht und kein Beleg vorhanden ist, welcher direkt auf einen gewöhnlichen Aufenthalt von S._ anfangs 2012 in Griechenland schliessen lassen müsste. Das Obergericht durfte deshalb willkürfrei feststellen, dem Beschwerdeführer sei der entsprechende Nachweis misslungen.
4.
Das HKÜ kann nur zur Anwendung gelangen, wenn das Kind seinen Aufenthalt in einem Vertragsstaat hatte, unmittelbar bevor es in einen anderen Vertragsstaat verbracht und dadurch ein Sorgerecht widerrechtlich verletzt worden ist (Art. 1 lit. a, Art. 3 Abs. 1 lit. a und Art. 4 HKÜ). Beim HKÜ handelt es sich folglich nicht um ein sog. allseitiges Übereinkommen, das erga omnes-Wirkung entfaltet. Ist der gewöhnliche Aufenthalt des Kindes in einem Vertragsstaat nicht nachgewiesen, kommt das HKÜ mithin nicht zur Anwendung. Dies ist angesichts des willkürfreien oberinstanzlichen Beweisergebnisses der Fall und folglich ist das Obergericht auf das Rückführungsgesuch zu Recht nicht eingetreten.
Fehlt es am Anwendungsbereich des Übereinkommens, so fällt auch eine auf <ref-law> gestützte Mediation zwischen den Eltern ausser Betracht, ist doch dieses Gesetz gemäss Ingress in Ausführung u.a. des Haager Rückführungsübereinkommens ergangen und bezieht sich <ref-law> offensichtlich auf das betreffende gerichtliche Verfahren. Das Obergericht hat deshalb ebenfalls zu Recht befunden, dass die übrigen Anträge bei fehlender Anwendbarkeit des Übereinkommens hinfällig seien.
5.
Zusammenfassend ergibt sich, dass die Beschwerde in Zivilsachen abzuweisen ist, soweit auf sie eingetreten werden kann. In Rückführungsverfahren werden gestützt auf Art. 26 Abs. 2 HKÜ keine Gerichtskosten erhoben und den Parteien - abgesehen von der Ausnahme bei einer Rückführungsverpflichtung (vgl. Art. 26 Abs. 4 HKÜ) -keine gegenseitigen Parteikosten auferlegt, was sinngemäss auch für ein Putativ-Rückführungsverfahren gelten muss. Infolge Entschädigung durch die Gerichtskasse ist das Gesuch der Beschwerdegegnerin um unentgeltliche Rechtspflege gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde in Zivilsachen wird abgewiesen, soweit darauf einzutreten ist.
2.
Es werden keine Gerichtskosten erhoben.
3.
Rechtsanwältin Annegret Lautenbach-Koch und Rechtsanwältin Heidi Frick-Moccetti werden aus der Gerichtskasse mit je Fr. 2'000.-- entschädigt.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, sowie der Zentralbehörde für Kindesentführung schriftlich mitgeteilt.
Lausanne, 18. April 2013
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Der Gerichtsschreiber: Möckli