Sachverhalt: A. Mit Entscheid vom 24. Oktober 2017 erteilte das Zivilgericht des Kantons Basel-Stadt A._ in der Betreibung Nr. xxx (Zahlungsbefehl vom 3. August 2017) die definitive Rechtsöffnung für die Unterhaltsbeiträge von Fr. 42'900.-- (März 2014 bis Mai 2015) plus Zins zu 5% ab 31. Oktober 2014 und von Fr. 71'000.-- (August 2015 bis Juli 2017) plus Zins zu 5% ab 16. Oktober 2016 sowie für die Parteientschädigungen von Fr. 2'500.-- (Verfahren vor Bundesgericht), Fr. 1'000.-- (Verfahren vor dem Regionalgericht Emmental-Oberaargau) und Fr. 1'771.20 (Verfahren vor dem Obergericht Bern), jeweils plus Zinsen. B. B._ wandte sich gegen diesen Rechtsöffnungsentscheid an das Appellationsgericht des Kantons Basel-Stadt, welches seine Beschwerde mit Entscheid vom 31. Mai 2018 abwies. C. Mit Eingabe vom 8. Juli 2018 ist B._ an das Bundesgericht gelangt. Der Beschwerdeführer beantragt, die Sache an das Zivilgericht zur Neubeurteilung zurückzuweisen, die erst- und zweitinstanzlichen Kostenentscheide aufzuheben und die Kosten dem Vertreter von A._ (Beschwerdegegnerin) aufzuerlegen. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten ist. Das Appellationsgericht beantragt die Abweisung der Beschwerde. Sollte der Beginn der Verzinsung der Unterhaltsforderungen auf die Anhebung der Betreibung angesetzt werden, ersucht es um eine entsprechende materielle Anpassung des angefochtenen Entscheides. Die Stellungnahmen sind dem Beschwerdeführer zur Wahrung seines Replikrechtes zugestellt worden.