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.

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 Obergerichts Bern, 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 die Beschwerde in Zivilsachen offen (Art. 75 Abs. 1 und Art. 90 BGG).
Mit ihr kann insbesondere die Verletzung von Bundesrecht (<ref-law>) und von Völkerrecht (<ref-law>) gerügt werden, wozu als Staatsvertrag auch das HKÜ gehört. Demgegenüber ist das Bundesgericht an die Sachverhaltsfeststellungen der Vorinstanz grundsätzlich gebunden (<ref-law>). Diesbezüglich kann einzig eine offensichtlich unrichtige, d.h. willkürliche Sachverhaltsfeststellung bzw. Beweiswürdigung gerügt werden, wofür das strenge Rügeprinzip zum Tragen kommt und appellatorische Ausführungen ungenügend sind (<ref-law>; <ref-ruling> E. 2.3 S. 266). Im Einzelnen wird im Sachzusammenhang darauf einzugehen sein.
Echte Noven sind im bundesgerichtlichen Verfahren grundsätzlich ausgeschlossen (<ref-ruling> E. 2.1 S. 344; <ref-ruling> E. 3.1.2 S. 123) und unechte sind nur insoweit zulässig, als erst der angefochtene Entscheid dazu Anlass gegeben hat (<ref-law>), was zu begründen ist (<ref-ruling> E. 3 S. 395).
Die Beschwerdegegnerin verlangt eine mündliche Verhandlung. Vor Bundesgericht findet eine solche aber nur ausnahmsweise statt und die Parteien haben grundsätzlich keinen Anspruch darauf (<ref-law>; Urteile 2C_844/2009 vom 22. November 2010 E. 3.2.3; 5A_880/2011 vom 20. Februar 2012 E. 1.5). Es ist nicht ersichtlich, inwiefern vorliegend vom Grundsatz abzuweichen wäre.
2.
In formeller Hinsicht rügt der Beschwerdeführer eine Verletzung des Anspruches auf ein faires Verfahren, weil die Vorinstanz von der Beschwerdegegnerin die Übersetzung der Gesuchsbeilagen 8-12 verlangt und diese offensichtlich ungenügende Google-Übersetzungen eingereicht habe. In der Folge habe das Obergericht seinen mündlichen Antrag, diese Beilagen aus den Akten zu weisen, abgewiesen, und die Beilagen in die Beweiswürdigung einbezogen.
Das Obergericht hat die Abweisung des Antrages auf Entfernung der Beilagen aus den Akten nicht näher begründet; diesbezüglich wird aber keine substanziierte Gehörsrüge erhoben.
Was sodann das Abstellen auf die Gesuchsbeilagen anbelangt, geht es um Fragen der Sachverhaltsfeststellung und Beweiswürdigung, weshalb der Beschwerdeführer Willkürrügen hätte erheben (vgl. E. 1) und im Übrigen substanziiert dartun müssen, inwiefern die Übersetzung mangelhaft und ihm dadurch ein Nachteil entstanden sein soll. Indem er dies nicht tut, stösst seine allgemeine Rüge, es sei ihm kein faires Verfahren gewährt worden, ins Leere.
3.
In der Sache selbst stellt sich vorab die Frage nach dem gewöhnlichen Aufenthaltsort der Kinder im Zeitpunkt des Verbringens durch den Vater. Wäre, wie dieser behauptet, in Spanien noch gar kein gewöhnlicher Aufenthalt begründet worden, sondern hätte er sich nach wie vor in der Schweiz befunden, so wäre das Rückführungsübereinkommen nicht anwendbar (vgl. Art. 1 lit. a i.V.m. Art. 4 HKÜ; PIRRUNG, in: J. von Staudingers Kommentar zum Bürgerlichen Gesetzbuch, Berlin 2009, Vorbem zu Art. 19 EGBGB, D 16 und D 34).
3.1. Was unter dem gewöhnlichen Aufenthalt des Kindes zu verstehen ist, wird in keinem der Haager Übereinkommen näher definiert. Der Begriff ist freilich vertragsautonom auszulegen und darunter wird gemeinhin der tatsächliche Mittelpunkt der Lebensführung des Kindes verstanden (<ref-ruling> E. 3 S. 122: "le centre effectif de la vie et de ses attaches"), welcher sich aufgrund der nach aussen erkennbaren tatsächlichen Umstände wie der Dauer des Aufenthaltes und den dadurch begründeten Beziehungen oder der voraussichtlichen Dauer des Aufenthalts und der damit zu erwartenden Integration ergibt (vgl. Urteile 5A_257/2011 vom 25. Mai 2011 E. 2.2; 5A_58/2016 vom 14. März 2016 E. 3). In der Regel fällt der gewöhnliche Aufenthalt mit dem Lebensmittelpunkt mindestens eines Elternteils zusammen; im Normalfall eines Umzugs - d.h. unter Vorbehalt einer Entführung - mit dem sorgeberechtigten Elternteil begründet ein Kind sofort einen gewöhnlichen Aufenthalt am neuen Ort (<ref-ruling> E. 4.1 S. 292; Urteile 5P.367/2005 vom 15. November 2005; 5A_650/2009 vom 11. November 2009 E. 5.2; 5A_665/2010 vom 2. Dezember 2010 E. 4.1; 5A_346/2012 vom 12. Juni 2012 E. 4.1; 5A_809/2012 vom 8. Januar 2013 E. 2.3.3; 5A_324/2014 vom 9. Oktober 2014 E. 5.2). Aus diesen Gründen geht das Bundesgericht im Zusammenhang mit der an den gewöhnlichen Aufenthalt des Kindes geknüpften Zuständigkeit für Sorgerechtsbelange (vgl. <ref-law>, Haager Kindesschutzübereinkommen, SR 0.211.231.011) auch davon aus, dass hängige Verfahren mit dem tatsächlichen Wegzug des Kindes gegenstandslos werden (<ref-ruling> E. 2.2.4 und 2.3.1 S. 591 f.; Urteile 5A_622/2010 vom 27. Juni 2011 E. 3 und 4; 5A_131/2011 vom 31. März 2011 E. 3.3.1: "un changement simultané de la compétence"); eine Ausnahme besteht einzig für den Wegzug in einen Staat, welcher das HKsÜ nicht unterzeichnet hat (<ref-ruling> E. 2.1 S. 4).
3.2. Das Obergericht ist in rechtlicher Hinsicht davon ausgegangen, dass für die Kinder unmittelbar mit dem Wegzug gewöhnlicher Aufenthalt in Spanien begründet worden sei. Es ist aufgrund der folgenden Sachverhaltselemente zu diesem Schluss gekommen: Wegzug zum neuen Lebenspartner; Absicht der Mutter zu definitivem Verbleib in Spanien; Abmeldung von Mutter und Kindern in der Schweiz; Anmeldung von Mutter und Kindern in Spanien am 28. Dezember 2015; Einschulung der Kinder bzw. definitive Einschulung von D._ und Abklärungen betreffend passende Einschulung für C._; Vorliegen einer väterlichen Zustimmung zum Wegzug und der dortigen Einschulung der Kinder; Abschluss einer Krankenversicherung in Spanien).
Diesen Tatsachenelementen setzt der Beschwerdeführer nichts entgegen. Er führt auch nicht aus (<ref-law>), inwiefern das Obergericht ausgehend von der betreffenden Tatsachenbasis zu falschen rechtlichen Schlüssen gelangt wäre.
3.3. Der Beschwerdeführer kritisiert einzig die Sachverhaltsfeststellung bzw. die obergerichtliche Beweiswürdigung im Zusammenhang mit der Abgabe seiner Zustimmung, dass die Mutter den Aufenthaltsort der Kinder nach Spanien verlegen durfte. Dies steht in keinem direkten Zusammenhang mit der Begründung eines neuen Aufenthaltsortes. Dennoch sei angesichts der längeren obergerichtlichen Ausführungen kurz Stellung genommen.
Der Beschwerdeführer hatte eine mit Mängeln behaftete Zustimmungserklärung geltend gemacht. Er habe vom neuen Lebenspartner seiner Frau nichts gewusst und sei von einer maximal sechsmonatigen "Auszeit" ausgegangen; seine Frau habe ihm vorgespiegelt, in Spanieneine alte Frau zu pflegen, welche als Gegenleistung für ihren Unterhalt aufkommen würde. Das Obergericht hat dies als unglaubwürdig angesehen, zumal der Vater selbst vor Ort war, um sich das zukünftige Zuhause wie auch die Schulen anzusehen und weitere Erkundigungen einzuziehen. Es ist beweiswürdigend der Darstellung der Mutter gefolgt, wonach es zur Trennung gekommen sei und sie ihren Ehemann vom neuen Partner in Spanien unterrichtet habe. Subsidiär ist das Obergericht davon ausgegangen, dass er von der neuen Beziehung jedenfalls habe ahnen müssen, zumal er vor Ort gewesen sei und dort auch Erkundigungen eingezogen habe.
Vor Bundesgericht bringt der Beschwerdeführer erneut vor, sie hätten sich nicht getrennt; ansonsten würde eine schriftliche Trennungsvereinbarung vorliegen, denn er sei schliesslich Rechtsanwalt. Seine Ehefrau habe einfach eine Auszeit gewollt und gesagt, in Spanien seien die Lebenshaltungskosten tiefer. Es sei gerichtsnotorisch, dass betrogene Ehemänner handgreiflich oder zumindest verbal ausfällig würden; dass seine Ehefrau nichts solches vorbringe, belege, dass er von ihrem neuen Lebenspartner nichts gewusst habe. Sie habe ihn mit Liebesbeteuerungen über ihre neue Bekanntschaft getäuscht, um ihn zu einer Zustimmungserklärung zu verleiten.
All diese Ausführungen werden in rein appellatorischer Form und ohne Bezug auf die ausführliche gegenteilige Beweiswürdigung durch das Obergericht vorgetragen. Aber selbst wenn der Beschwerdeführer zulässige Willkürrügen erhoben hätte, könnten sie keinen Erfolg haben: Der Wegzug eines Ehegatten bedarf keinerlei Genehmigung durch den anderen; zustimmungsbedürftig ist allein die Verlegung des Aufenthaltsortes der Kinder ins Ausland bei geteiltem Sorgerecht (<ref-law>; ausführlich zum Ganzen das zur Publikation bestimmte Leiturteil 5A_450/2015 vom 11. März 2016 E. 2.3-2.8). In Bezug auf die Kinder kann es aber keinen Unterschied machen, auf welchen Motiven der Wegzug der Mutter beruhte. Relevant für die Willensbildung des Beschwerdeführers konnte einzig die Frage sein, ob die Kinder in Spanien gut untergebracht und betreut sowie adäquat beschult würden. Diesbezüglich steht fest, dass der Vater sich die Umgebung, in welche die Kinder zu leben kämen, und die für sie vorgesehenen Schulen vorgängig angesehen hat und er im Übrigen um die sprachlichen und gesundheitlichen Probleme der Kinder (worauf noch zurückzukommen sein wird) bestens im Bild war. Seine Zustimmung zur Verlegung des Aufenthaltsortes der Kinder basierte mithin auf umfassender Kenntnis der für die betreffende Frage topischen Sachverhaltselemente; sie war und ist mithin mängelfrei. Nur der Vollständigkeit halber sei überdies festgehalten, dass der Beschwerdeführer seine Zustimmung, welche als Gestaltungserklärung ohnehin grundsätzlich unwiderruflich ist, zeitlich erst nach dem Verbringen der Kinder in die Schweiz widerrufen hat.
Gleiches gilt für die - bereits obergerichtlich nicht näher belegte - Behauptung, die Mutter sei mit den Kindern nach W._ statt U._ gezogen: Auch hier liegt in Bezug auf die ausführliche Sachverhaltsfeststellung und Beweiswürdigung des Obergerichtes keine Willkürrüge vor. Abgesehen davon liegen die Orte nur wenige Kilometer entfernt und geht es um die gleiche Einschulung, so dass ohnehin nicht zu sehen wäre, welche Änderung sich im Verhältnis Spanien-Schweiz in Bezug auf das Vater-Kind-Verhältnis ergeben könnte und inwiefern die Zustimmungserklärung deshalb mangelhaft hätte sein können.
3.4. Als Zwischenergebnis ist festzuhalten, dass die beiden Kinder vor dem Verbringen in die Schweiz durch den Vater ihren gewöhnlichen Aufenthalt in Spanien hatten. Das Haager Rückführungsübereinkommen findet Anwendung.
4.
Sinngemäss bestritten wird sodann das Vorliegen einer widerrechtlichen Sorgerechtsverletzung im Sinn von Art. 3 lit. a i.V.m. Art. 5 HKÜ, indem der Beschwerdeführer geltend macht, es fehle an einer tauglichen Widerrechtlichkeitsbescheinigung im Sinn von Art. 15 HKÜ (dazu E. 4.2) und gemäss rechtskräftiger Verfügung der Staatsanwaltschaft Berner Oberland sei das Verfahren wegen Entziehens von Minderjährigen gegen ihn nicht an die Hand genommen worden (dazu E. 4.3).
4.1. Das Obergericht hat festgestellt, dass den verheirateten Eltern in der Schweiz das gemeinsame Sorgerecht zukam, und es ist davon ausgegangen, dass dies auch für Spanien der Fall gewesen sei. In Bezug auf das spanische Recht hat es auf eine Erklärung des Generalkonsuls von Spanien in Bern verwiesen, wonach sich dieser zu <ref-law>/ES geäussert und festgehalten habe, ein Elternteil, der ohne triftigen Grund sein minderjähriges Kind entführe, werde mit Freiheitsstrafe und dem Verlust der Ausübung der elterlichen Sorge bestraft. Das Obergericht hat befunden, dass zivilrechtlich nicht erlaubt sein könne, was strafrechtlich verboten sei. Wie nach schweizerischem Recht setze also ein (erneuter) Wechsel des Aufenthaltsortes der Kinder auch nach spanischem Recht die Zustimmung beider Elternteile voraus.
4.2. Der Beschwerdeführer macht geltend, es liege keine taugliche Widerrechtlichkeitsbescheinigung im Sinn von Art. 15 HKÜ vor, weil sich der Generalkonsul nur zum spanischen Strafrecht, nicht aber zum spanischen Sorgerecht äussere.
Es trifft zu, dass die Erklärung des spanischen Generalkonsuls keine topischen Aussagen macht, indem sie sich einzig zum spanischen Strafrecht, nicht aber zur Sorgerechtslage unmittelbar vor dem Verbringen der Kinder in die Schweiz äussert. Indes handelt es sich bei Art. 15 HKÜ um eine kann-Vorschrift; weder ist das Einholen einer Widerrechtlichkeitsbescheinigung eine Voraussetzung für den Rückführungsentscheid (Urteil 5A_577/2014 vom 21. August 2014 E. 3.3; PIRRUNG, a.a.O., D 79) noch ist der Rückführungsrichter daran inhaltlich gebunden (PIRRUNG, a.a.O., D 79). Entsprechend kommt es nicht darauf an, ob die Bescheinigung topische Äusserungen enthält.
Der Beschwerdeführer müsste deshalb im Rahmen seiner Begründungspflicht gemäss <ref-law> darlegen, inwiefern die Annahme des Obergerichtes, es liege eine widerrechtliche Sorgerechtsverletzung vor, im Ergebnis unzutreffend ist. Dies tut er nicht. Ohnehin aber ist das Bestehen eines mütterlichen Sorgerechts und dessen Verletzung durch das einseitige Verbringen der Kinder in die Schweiz offensichtlich. Das Rückführungsgericht darf das ausländische Recht direkt feststellen (<ref-ruling> E. 2.1.2 S. 697, vgl. auch <ref-law>) und dieses sei nachfolgend kurz dargelegt.
Wem das Aufenthaltsbestimmungsrecht über das Kinder zukam - was entscheidend ist für die Frage der widerrechtlichen Sorgerechtsverletzung im Sinn von Art. 3 und 5 HKÜ -, bestimmt sich nach dem internationalen Privatrecht am gewöhnlichen Aufenthaltsort des Kindes unmittelbar vor dem Verbringen (<ref-ruling> E. 3.5 S. 362), wobei auch ein allfälliger Renvoi zu beachten ist (Urteil 5A_764/2009 vom 11. Januar 2010 E. 3.1). Art. 9 Abs. 4 Código civil español (CCes) verweist seit dem 1. Januar 2011 für den Inhalt und die Ausübung des Sorgerechtes direkt auf das HKsÜ. Zum gleichen Ergebnis hätte allerdings auch die frühere Rechtslage geführt (vgl. BERGMANN/FERID, Internationales Ehe- und Kindschaftsrecht, Spanien 182. Lieferung, S. 37 f.) : Charakter und Inhalt des Kindschaftsverhältnisses sowie die Beziehungen zwischen Eltern und Kindern richteten sich nach dem Personalstatut des Kindes, welches nach Art. 9 Abs. 1 CCes durch die Staatsangehörigkeit bestimmt wird; aufgrund der schweizerischen Staatsangehörigkeit von C._ und D._ wären mithin Art. 82 Abs. 1 und 3 i.V.m. <ref-law> anwendbar gewesen, welche ebenfalls auf das HKsÜ verweisen.
Ausgehend von der Anwendbarkeit des HKsÜ stellt sich die Frage, welche Auswirkungen der seinerzeitige Wegzug der Kinder nach Spanien auf die Sorgerechtslage hatte. Die Antwort gibt <ref-law>, wonach das in der Schweiz den Eltern gemeinsam zustehende Sorgerecht auch am neuen Aufenthaltsort der Kinder in Spanien weitergilt (<ref-law>), wobei sich dessen Ausübung nach dem Recht des Staates des gewöhnlichen Aufenthaltes der Kinder bemisst (<ref-law>). Die elterliche Sorge des schweizerischen Rechts entspricht der spanischen "patria potestad" (elterliche Gewalt) im Sinn von Art. 154 ff. CCes. Nach spanischem Recht umfasst die patria potestad u.a. die Befugnis, die Kinder bei sich zu haben (Art. 154 Abs. 2 CCes). Daraus ergibt sich die Aufenthaltsbestimmungsbefugnis (Urteile 5A_441/2010 vom 7. Juli 2010 E. 4.3.1; 5A_550/2012 vom 10. September 2012 E. 3.3.2; beide Entscheide betreffen Rückführungen nach Spanien). Nicht entscheidend ist die - einzig im Zusammenhang mit der Trennung und Scheidung in Art. 90 ff. CCes geregelte - Obhut (guarda y custodia, vgl. zur analogen Lage nach katalanischem Recht, welches in jener Konstellation als innerspanisches Kollisionsrecht zur Anwendung kam: Urteil 5A_537/2012 vom 20. September 2012 E. 2), welche durchaus auch geteilt sein kann (sog. guarda y custodia compartida aufgrund entsprechender Scheidungsvereinbarung, Art. 92 Abs. 5 CCes, oder richterlicher Anordnung, Art. 92 Abs. 8 CCes).
Wie dies für das schweizerische Recht der Fall ist, wird die patria potestad auch nach spanischem Recht grundsätzlich durch beide Elternteile gemeinsam ausgeübt (Art. 156 Abs. 1 CCes). Leben die Eltern getrennt, so wird sie durch denjenigen Elternteil ausgeübt, bei welchem die Kinder leben (Art. 156 Abs. 7 CCes). Ob dies sogar zur Folge hat, dass die Mutter im vorliegenden Fall die elterliche Sorge allein ausübte und ihr das Aufenthaltsbestimmungsrecht in Spanien alleine zustand, kann offen bleiben. Jedenfalls verfügte sie auch dort mindestens über das gemeinsame Sorgerecht. Einem Verbringen der Kinder in die Schweiz hat sie nach den unbestrittenen obergerichtlichen Sachverhaltsfeststellungen nie zugestimmt. Folglich liegt im Verbringen eine widerrechtliche Sorgerechtsverletzung im Sinn von Art. 3 und 5 HKÜ begründet.
4.3. Im Zusammenhang mit der Verfügung der Staatsanwaltschaft Berner Oberland stellt sich die Frage, ob es sich um ein echtes oder unechtes Novum handelt, weil sie am 11. April 2016 und der angefochtene Entscheid am 18. April 2016 ergangen ist, jedoch die Verfügung darin keinen Eingang mehr finden konnte. Inwiefern der Beschwerdeführer vor diesem Hintergrund die Verfügung der Staatsanwaltschaft dem Bundesgericht überhaupt präsentieren kann (vgl. E. 1), kann letztlich offen bleiben, weil er daraus ohnehin nichts für seinen Standpunkt ableiten kann.
Mit dieser Verfügung nahm die Staatsanwaltschaft Berner Oberland das Verfahren gegen den Beschwerdeführer wegen Entziehens von Minderjährigen gestützt auf <ref-law> nicht an die Hand. Eine solche Verfügung hat aber selbstredend keinen Einfluss auf die Sorgerechtslage, wie sie im Zeitpunkt des Verbringens der Kinder in die Schweiz effektiv bestand. Zum anderen beruht sie auf unhaltbaren und in Missachtung der publizierten bundesgerichtlichen Rechtsprechung ergangenen Überlegungen, indem festgehalten wird, beide Eltern hätten nach wie vor die elterliche Sorge und damit das Aufenthaltsbestimmungsrechts, weshalb der Vater als Inhaber dieses Rechtes nicht Täter sein könne.
Bereits nach der bis 30. Juni 2014 geltenden Fassung von <ref-law> war der Mitinhaber des Aufenthaltsbestimmungsrechtes geschützt und damit der andere Mitinhaber strafbar, wenn er ohne Zustimmung den Aufenthaltsort des Kindes änderte (<ref-ruling> E. 2a S. 63; <ref-ruling> E. 2a S. 15 f.; <ref-ruling> E. 3.4 S. 360; <ref-ruling> E. 5.3.1 S. 210 f.), denn seit je bestand der Grundsatz, dass sich aus dem Zivilrecht ergibt, wer Träger des Aufenthaltsbestimmungsrechtes ist (<ref-ruling> E. 3.3 S. 160; <ref-ruling> E. 5.3.1 S. 210). Auch für die Lehre war bereits für das alte Recht durchwegs klar, dass als Täter jedermann in Frage kam, dem das Aufenthaltsbestimmungsrecht über das Kind nicht allein und uneingeschränkt zustand (ECKERT, Basler Kommentar, N. 8 zu <ref-law>; STRATENWERTH/ WOHLER, Handkommentar, N. 2 zu <ref-law>; TRECHSEL/PIETH, Praxiskommentar, N. 2 zu <ref-law>).
Noch viel deutlicher wird dies aufgrund der Fassung von <ref-law>, wie sie seit dem 1. Juli 2014 gilt und vorliegend von der Staatsanwaltschaft zu beachten gewesen wäre. Angelpunkt der Sorgerechtsnovelle (Bundesgesetz vom 21. Juni 2013, AS 2014 357, in Kraft seit 1. Juli 2014) ist, dass das Sorgerecht zivilstandsunabhängig grundsätzlich beiden Elternteilen gemeinsam zukommt (Art. 296 Abs. 1, Art. 298 Abs. 1 und Art. 298b Abs. 2 ZGB) und das Aufenthaltsbestimmungsrecht neu nicht mehr im Obhutsrecht enthalten (vgl. zur alten Rechtslage <ref-ruling>), sondern ein Teil der elterlichen Sorge ist (<ref-law>). Das Aufenthaltsbestimmungsrecht steht folglich bei gemeinsamer elterlicher Sorge den Eltern gemeinsam zu und insbesondere die Verlegung des Aufenthaltsortes des Kindes ins Ausland bedarf bei gemeinsamem Sorgerecht ausnahmslos der Zustimmung des anderen Elternteils oder eines substituierenden gerichtlichen oder behördlichen Entscheides (<ref-law>). Im Zusammenhang mit der Sorgerechtsnovelle wurde der Wortlaut von <ref-law> an die neue zivilrechtliche Ausgestaltung angepasst; strafbar ist, wer eine minderjährige Person dem Inhaber des Rechts zur Bestimmung des Aufenthaltsortes entzieht oder sich weigert, sie ihm zurückzugeben. Sowohl der Täter als auch das Opfer kann ein über das gemeinsame Sorge- und damit Aufenthaltsbestimmungsrecht verfügender Elternteil sein; aufgrund der Neugestaltung des elterlichen Sorgerechts (Grundsatz der gemeinsamen Sorge) wird es in der Strafrechtspraxis sogar die primäre Konstellation sein, dass sich als Täter und Opfer die beiden Elternteile gegenüberstehen.
4.4. Nach dem Gesagten stand der Mutter im Zeitpunkt des Verbringens der Kinder durch den Vater das Aufenthaltsbestimmungsrecht über die Kinder (allein oder gemeinsam mit dem Vater) zu und hat sie nach den unbestrittenen Sachverhaltsfeststellungen dem Verbringen in die Schweiz nicht zugestimmt. Die Sorgerechtsverletzung ist somit widerrechtlich, was grundsätzlich die sofortige Rückgabepflicht der Kinder auslöst (Art. 12 Abs. 1 HKÜ), soweit nicht Ausschlussgründe gegeben sind.
5.
Zur Debatte steht in erster Linie der Ausschlussgrund der schwerwiegenden Gefahr für die Kinder (Art. 13 Abs. 1 lit. b HKÜ) aufgrund ihrer gesundheitlichen Beeinträchtigungen, namentlich im Zusammenhang mit der Sprachentwicklung.
5.1. Das Obergericht hat die schwerwiegende Gefahr verneint mit der Begründung, dass sich die Mutter des Handlungsbedarfes nicht nur bewusst sei, sondern in Spanien auch die nötigen Behandlungsmassnahmen für die Kinder eingeleitet habe. Sodann seien dem Vater im Zeitpunkt der Abgabe seiner Zustimmung zum Wegzug der Kinder sowohl die Behinderungen von C._ (Bericht der UPD vom 14. April 2015: Trisomie 21, Störung aus dem autistischen Spektrum, deutliche Sprachentwicklungsstörung, deutliche psychomotorischer Entwicklungsrückstand) als auch die Sprachentwicklungsstörung bei D._ bekannt gewesen. Folglich hätten ihm im Herbst 2015 die sprachlichen Hürden bei einem Umzug nach Spanien als vertretbar erschienen und in der Zwischenzeit habe sich bei den Kindern nichts geändert, zumal sich in keinem der Arztberichte eine Stütze für die Behauptung des Vaters finde, C._ werde ohne Behandlung zusätzlich ein "Locked-in-Syndrom" entwickeln. Ferner lasse sich keinem der vom Vater eingereichten Arztberichte entnehmen, dass die Kinder nicht auch in Spanien adäquat behandelt werden könnten.
5.2. Vor Bundesgericht versucht der Beschwerdeführer erneut, in allgemeiner Weise eine Verletzung von Art. 13 Abs. 1 lit. b HKÜ im Zusammenhang mit den Defiziten der beiden Söhne geltend zu machen.
Was den Sachverhalt anbelangt, lässt es der Beschwerdeführer aber wiederum bei appellatorischen Ausführungen bewenden, welche überdies vage bleiben (für die behauptete Entwicklung eines "Locked-in-Syndroms" wird beispielsweise auf eine angebliche telefonische ärztliche Auskunft verwiesen).
5.3. Was die schwerwiegende Gefahr als Rechtsbegriff anbelangt, so ist der Ausschlussgrund von Art. 13 Abs. 1 lit. b HKÜ nach allgemeiner Auffassung restriktiv auszulegen (Urteile 5A_913/2010 vom 4. Februar 2011 E. 5.2; 5A_246/2014 vom 28. April 2014 E. 3.1; 5A_229/2015 vom 30. April 2015 E. 6.1; Europäischer Gerichtshof für Menschenrechte, Grosse Kammer, Entscheid Nr. 27853/09 vom 26. November 2013 Rz. 107; Bundesverfassungsgericht Deutschland, Entscheid BvR 1206/98 vom 29. Oktober 1998 Rz. 48; Oberster Gerichtshof Österreich, Entscheide 5Ob47/09m vom 12. Mai 2009 und 2Ob103/09z vom 16. Juli 2009). Eine schwerwiegende Gefahr liegt beispielsweise vor bei einer Rückführung in ein Kriegs- oder Seuchengebiet oder wenn zu befürchten ist, dass das Kind nach der Rückgabe misshandelt oder missbraucht wird, ohne dass die Behörden rechtzeitig einschreiten würden, während anfängliche Sprach- und Reintegrationsschwierigkeiten typischerweise keine schwerwiegende Gefahr darstellen (vgl. <ref-ruling> E. 3 S. 535; Urteile 5A_913/2010 vom 4. Februar 2011 E. 5.1; 5A_674/2011 vom 31. Oktober 2011 E. 3.2; 5A_840/2011 vom 13. Januar 2012 E. 3.1; 5A_229/2015 vom 30. April 2015 E. 6.1).
Für die Behinderungen von C._ (Trisomie 21, Autismus) dürfte es auch in Spanien ein Betreuungsangebot geben. In Bezug auf die sprachlichen Defizite der beiden Kinder wird eine adäquate Behandlung in Spanien aber insofern schwieriger zu bewerkstelligen sein, als sie offenbar vorwiegend die Muttersprachen der Eltern (tschechisch bzw. slowakisch) und sodann Berndeutsch sprechen, während Spanisch für sie neu ist. Dies begründet aber noch keine schwerwiegende Gefahr im beschriebenen Sinn, ansonsten Eltern mit Kindern nie in ein für sie neues Sprachgebiet ziehen dürften. Dies sah wenige Monate zuvor offensichtlich auch der Beschwerdeführer so, ansonsten er nicht die Zustimmung zum Wegzug nach Spanien erteilt hätte.
Ein Verbleib der Kinder in der Schweiz, welchen angesichts der Behandlungsbedürftigkeit bezüglich Sprachentwicklung auch die Kindesvertreterin beantragt, würde sodann faktisch daran scheitern bzw. die Kinder in eine noch schwierigere Lage bringen, als die Verurteilung des Vaters zu einer unbedingten Gefängnisstrafe von 28 Monaten mit der Abweisung der hiergegen erhobenen Beschwerde durch das Bundesgericht (Urteil 6B_629/2015 vom 7. Januar 2016) rechtskräftig geworden worden ist. Die Mutter bringt denn auch wiederholt vor, der Vater habe die Kinder allein deshalb aus Spanien entführt und zu sich in seinen eigenen Haushalt genommen, um dem Strafvollzug zu entgehen. Was immer die Motive des Vaters für die Kindesentführung gewesen sein mögen und inwieweit er seither der Mutter den Zugang zu den Kindern verwehrt oder jedenfalls erschwert, kann im Detail offen bleiben: Er wird demnächst seine Gefängnisstrafe antreten müssen, woran Betreuungspflichten nichts ändern (vgl. Urteil 6B_312/2016 vom 23. Juni 2016 E. 1.5.3), weshalb die Kinder selbst im Rahmen eines materiellen Entscheides - welchen das Rückführungsgericht freilich gerade nicht treffen darf (Art. 16 und 19 HKÜ) - bei der Mutter in Spanien unterzubringen wären (vgl. ausführlich zur materiellrechtlichen Entscheidung betreffend Verlegung des Aufenthaltsortes von Kindern im Sinn von <ref-law> und diesbezüglich betreffend die Frage der tatsächlichen Betreuungsmöglichkeit der Elternteile: zur Publikation bestimmtes Urteil 5A_450/2015 vom 11. März 2016 E. 2.7).
5.4. Ferner bringt der Vater in der Replik vor, die Mutter habe der Einschulung von D._ in der Sprachheilschule X._ zugestimmt, weshalb sich die Frage stelle, ob sie noch ein Interesse an der Rückführung der Kinder habe. Die Mutter stellt in der Duplik klar, dass die Zustimmung einzig erfolgt sei, um einen Platz in der Sprachheilschule sicherzustellen für den Fall, dass die Beschwerde durch das Bundesgericht gutgeheissen und die Kinder in der Schweiz verbleiben würden.
Der Vater spricht mit seinem Vorbringen sinngemäss den Ausschlussgrund der nachträglichen Genehmigung des widerrechtlichen Verbringens gemäss Art. 13 Abs. 1 lit. a HKÜ an. Dass die Mutter einem Verbleiben der Kinder in der Schweiz zugestimmt hätte, behauptet aber nicht einmal er selbst. Wenn die Mutter einer zwischenzeitlichen Einschulung von D._ in einem geeigneten Institut zugestimmt hat, liegt darin keine Zustimmung im Sinn von Art. 13 Abs. 1 lit. a HKÜ; vielmehr zeugt dies davon, dass sie den besonderen Bedürfnissen der Kinder gerecht wird und das Sorgerecht zu deren bestem Interesse ausübt.
5.5. Nach dem Gesagten sind nicht nur keine Ausschlussgründe für eine Rückführung der Kinder zur Mutter, welche bislang stets deren Hauptbetreuungsperson war, ersichtlich, sondern wäre dies sogar bei einer materiellen Entscheidung aufgrund des Kindeswohls geboten.
6.
Zusammenfassend ergibt sich, dass die Beschwerde abzuweisen ist, soweit auf sie eingetreten werden kann. Bundesgerichtsurteile werden am Tag ihrer Ausfällung rechtskräftig (<ref-law>). Die Anordnungen im Urteil des Obergerichtes vom 18. April 2016 (Übergabeverpflichtung des Vaters innerhalb von 24 Stunden ab Erhalt des obergerichtlichen Entscheides, Zwangsvollstreckungsmodalitäten) sind mithin sofort vollziehbar; insbesondere ist der Vater unmittelbar ab dem Erhalt des vorliegenden Entscheides zur Übergabe der Kinder verpflichtet.
7.
Es sind keine Gerichtskosten zu erheben (Art. 26 Abs. 2 HKÜ). Die Kosten für die Vertretung der Mutter könnten theoretisch dem Beschwerdeführer auferlegt werden (Art. 26 Abs. 4 HKÜ). Davon sieht das Bundesgericht aber praxisgemäss ab, wenn die finanziellen Verhältnisse nicht speziell gut sind. Nach den Ausführungen der Mutter ist der Beschwerdeführer überschuldet und im Rahmen seiner strafrechtlichen Verurteilung wurde über ihn auch ein vierjähriges Berufsverbot betreffend Ausübung einer selbständigen Tätigkeit als Fürsprecher/ Rechtsanwalt verhängt. Der Rechtsvertreter der Mutter ist folglich gestützt auf Art. 26 Abs. 2 HKÜ aus der Bundesgerichtskasse zu entschädigen. Gleiches gilt ohnehin für die Kindesvertreterin. Das Gesuch um unentgeltliche Rechtspflege der Mutter ist nach dem Gesagten gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit auf sie einzutreten ist.
2.
Es werden keine Gerichtskosten erhoben.
3.
Rechtsanwalt Roger Lerf wird mit Fr. 2'000.-- und Fürsprecherin Sabine Schmutz mit Fr. 500.-- aus der Bundesgerichtskasse entschädigt.
4.
Die Regionalpolizei Berner Oberland, Stationierte Polizei V._, wird ersucht, dem Beschwerdeführer A._, das Original des vorliegenden Urteils persönlich gegen Empfangsbestätigung sofort polizeilich zuzustellen, dabei das Datum und die Uhrzeit der Zustellung in der Empfangsbestätigung festzuhalten und eine Kopie der Empfangsbestätigung unverzüglich dem Bundesgericht, II. zivilrechtliche Abteilung, dem Obergericht des Kantons Bern, 1. Zivilkammer, sowie dem kantonalen Jugendamt zu melden.
5.
Dieses Urteil wird dem Beschwerdeführer (unter polizeilicher Übergabe) sowie der Beschwerdegegnerin, der Kindesvertreterin, dem Obergericht des Kantons Bern, 1. Zivilkammer, dem Jugendamt des Kantons Bern und dem Bundesamt für Justiz, Zentralbehörde für Kindesentführungen, schriftlich mitgeteilt.
Lausanne, 8. August 2016
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Der Gerichtsschreiber: Möckli