Sachverhalt: A. Aus der Nachlassmasse der R._ erwarben X._ und Y._ im Jahr 2005 die S._ AG und dazugehörende Gesellschaften. In der Folge gerieten sie einen Konflikt, den sie mit einem zwischen den 16 beteiligten Parteien geschlossenen und von ihnen so betitelten "Entflechtungsvertrag" vom 12. Juni 2008 zu lösen suchten. Darin wurde u.a. vereinbart, dass X._ rückwirkend per 31. Dezember 2007 seine 245 Namenaktien der T._ AG für Fr. 60 Mio. an Y._ verkauft, wobei der Kaufpreis durch Verrechnung mit Gegenforderungen sowie der Einräumung eines novierenden Darlehens über Fr. 45'509'490.-- zu tilgen ist, bestehend aus einer Akontozahlung von Fr. 2 Mio. und einem Restdarlehen von Fr. 43'509'490.--. Als Sicherheiten sollten X._ zwei Schuldbriefe über je Fr. 20'000'000.-- auf Liegenschaften der U._ AG als Drittpfandgeberin sowie V._ (Einräumung von Beteiligungen) zustehen. Die Akontozahlung wurde am 15. Juli 2008 ausgeführt. Das Restdarlehen wurde gemäss Entflechtungsvertrag spätestens am 31. August 2008 fällig. Es erfolgte keine Zahlung. B. In der Folge leitete X._ gegen Y._ für Fr. 43'509'490.-- nebst Zins zu 6% seit 12. Juni 2008 die Betreibung Nr. ... des Betreibungsamtes A._ ein. Nachdem Y._ Rechtsvorschlag erhoben hatte, stellte X._ ein Gesuch um provisorische Rechtsöffnung, welches der Bezirksgerichtspräsident Plessur am 19. November 2008 abwies, unter Auferlegung der Verfahrenskosten von Fr. 2'000.-- und der Verpflichtung, Y._ ausseramtlich mit Fr. 24'775.-- zu entschädigen. Mit Urteil vom 6. Mai 2009 setzte das Kantonsgericht Graubünden die ausseramtliche Entschädigung auf Fr. 17'458.-- fest, wies aber im Übrigen die Beschwerde von X._ ab. C. Gegen dieses Urteil hat X._ am 10. Juni 2009 eine Beschwerde in Zivilsachen erhoben mit den Begehren um Erteilung der provisorischen Rechtsöffnung für Fr. 43'509'490.-- nebst Zins zu 6% seit 12. Juni 2008 in der Betreibung Nr. ... des Betreibungsamtes A._, eventualiter um Rückweisung der Sache zur neuen Entscheidung. Mit Vernehmlassung vom 20. Juli 2009 schliesst das Kantonsgericht auf Beschwerdeabweisung. Der Beschwerdegegner verlangt in seiner Vernehmlassung vom 28. August 2009 die Abweisung der Beschwerde, soweit darauf einzutreten sei. Der Beschwerdeführer hat am 3. September 2009 zur Vernehmlassung des Kantonsgerichts eine Stellungnahme eingereicht. Der Beschwerdegegner hat am 18. September 2009 weitere Unterlagen nachgereicht.