Sachverhalt: A. A._ und B._ sind die seit 1998 verheirateten Eltern von C._ (geb. 2007) und D._ (geb. 2009). C._ leidet am Down-Syndrom (Trisomie 21) und an Autismus. D._ leidet an einer Sprachentwicklungsstörung im Rahmen einer allgemeinen Entwicklungsverzögerung. B. Am 25. Oktober 2015 gab der Vater gegenüber der Mutter die schriftliche Erlaubnis, mit den Kindern nach U._ in Spanien umzuziehen und sie dort in näher bezeichneten Schulen einzuschulen; am 14. Dezember 2015 stellte er ihr überdies eine Vertretungsvollmacht gegenüber Schulen und Ärzten aus. Nach Abmeldung in der Schweiz reiste die Mutter mit den Kindern am 26. Dezember 2015 nach Spanien, wo sie sich und diese am 28. Dezember 2015 anmeldete. Anfangs Januar 2016 wurde D._ eingeschult, während für C._ zunächst noch weitere Abklärungen nötig waren. Ende Januar 2016 reiste der Vater besuchshalber nach Spanien. Dort verbrachte er zunächst während einigen Tagen regelmässig Zeit mit seinen Söhnen. In der Folge nahm er diese ohne Wissen der Mutter in die Schweiz, wo er am 5. Februar 2016 eintraf und die Kinder bei der Gemeinde V._ anmeldete. Am 8. Februar 2016 schrieb er der Mutter eine SMS, wonach er sein Einverständnis, dass sie mit den Kindern in Spanien leben dürfe, widerrufe. Mit Brief vom 7. März 2016 teilte er ihr zudem mit, dass die Einwilligung zum Umzug nach Spanien infolge Täuschung unverbindlich gewesen sei. C. Am 17. Februar 2016 stellte die Mutter ein Gesuch um Rückführung der beiden Kinder. Am 21. März 2016 wurde D._ durch Dr. phil. E._ angehört; auf eine Anhörung von C._ wurde angesichts der unzumutbaren Belastung (Down-Syndrom und Autismus) verzichtet. Die Parteien wurden anlässlich der Hauptverhandlung am 31. März 2016 angehört. Mit Entscheid vom 18. April 2016 verpflichtete das Obergericht des Kantons Bern den Vater, die beiden Kinder innert 24 Stunden ab Erhalt des Entscheides der Mutter zur Rückführung nach Spanien zu übergeben, unter Regelung der weiteren Modalitäten und Zwangsvollstreckungsmassnahmen bei unterbleibender Folgeleistung. D. Gegen diesen Entscheid hat der Vater am 19. April 2016 eine Beschwerde eingereicht mit dem Begehren um dessen Aufhebung. Mit Verfügung vom 19. April 2016 wurde superprovisorisch die aufschiebende Wirkung erteilt. Mit Vernehmlassung vom 29. April 2016 ersuchte die Kindesvertreterin um Gutheissung der Beschwerde. Gleichentags reichte der Vater eine ausführliche Beschwerdebegründung nach. Mit Vernehmlassung vom 2. Mai 2016 schloss die Mutter auf Abweisung der Beschwerde; ferner verlangte sie die unentgeltliche Rechtspflege. Mit Verfügung vom 5. Mai 2016 wurde der Beschwerde die aufschiebende Wirkung erteilt. Am 31. Mai 2016 reichte die Mutter eine Vernehmlassung zur nachgereichten Beschwerdebegründung des Vaters ein. Am 16. bzw. 27. Juni 2016 replizierten und duplizierten die Eltern. Am 15. Juli 2016 reichte der Beschwerdeführer eine Triplik ein.