Sachverhalt: A. A._ (Beklagter, Beschwerdeführer) war einziger Aktionär der C._ AG. Zwischen A._ und der B._ AG (Klägerin, Beschwerdegegnerin) bestand angeblich ein Treuhandverhältnis. Mit Kaufvertrag vom 1. Juli 1999 erwarb die D._ AG von A._ 89 Namenaktien der C._ AG. Die B._ AG war am Verkaufsprozess beteiligt. Mit Schreiben vom 29. November 2007 kündigte A._ das Vertragsverhältnis mit der B._ AG per 31. Dezember 2007. A._ betrieb die B._ AG mit Zahlungsbefehl Nr. xxx des Betreibungsamts Dietikon vom 9. Juni 2008 für einen Betrag von Fr. 1 Mio. nebst Zins zu 5 % seit 6. Juni 2008. Als Forderungsgrund wurde angegeben: "Kaufpreis- und Schadenersatzansprüche im Zusammenhang mit dem Verkauf der C._ AG an die D._ AG unter allen Titeln, insbesondere deliktischer und auftragsrechtlicher Natur, dies alles unter dem Vorbehalt der Nachforderung". Die Betriebene erhob Rechtsvorschlag. B. B.a. Am 29. April 2011 klagte die B._ AG beim Bezirksgericht Höfe mit den folgenden Rechtsbegehren: "1. Es sei festzustellen, dass die vom Beklagten in der Betreibung Nr. xxx des Betreibungsamtes Dietikon (Zahlungsbefehl vom 9.6.08) geltend gemachte Schuld [der Klägerin] von Fr. 1'000'000.00 nicht besteht. 2. Es sei das Betreibungsamt Dietikon/ZH anzuweisen, die Betreibung Nr. xxx gegen [die Klägerin] aus dem Register zu löschen. 3. Im Sinne einer vorsorglichen Massnahme sei für die Dauer des Verfahrens die Betreibung vorläufig einzustellen, alles unter Kosten- und Entschädigungsfolgen zulasten des Beklagten." Mit Urteil vom 21. Mai 2014 stellte das Bezirksgericht Höfe fest, dass die vom Beklagten in der Betreibung Nr. xxx des Betreibungsamts Dietikon geltend gemachte Schuld der Klägerin von Fr. 1 Mio. nicht bestehe (Dispositiv-Ziff. 1). Zudem wies es das Betreibungsamt Dietikon an, den Registereintrag in der Betreibung Nr. xxx gegen die Klägerin gemäss Art. 8a SchKG keinem Dritten bekannt zu geben (Dispositiv-Ziff. 2). Das Rechtsbegehren nach Antrags-Ziffer 3 wies das Bezirksgericht ab (Dispositiv-Ziff. 3). Die Gerichtskosten von insgesamt Fr. 16'148.80 auferlegte es dem Beklagten (Dispositiv-Ziff. 4), den es zudem zu einer Parteientschädigung von Fr. 25'000.-- an die Klägerin verpflichtete (Dispositiv-Ziff. 5). B.b. Der Beklagte focht den bezirksgerichtlichen Entscheid beim Kantonsgericht Schwyz mit Berufung an. Mit Beschluss vom 22. Juni 2015 hob das Kantonsgericht Dispositiv-Ziffern 1 und 2 des Urteils des Bezirksgerichts Höfe vom 21. Mai 2014 auf und schrieb das Verfahren zufolge Gegenstandslosigkeit ab (Dispositiv-Ziff. 1 Abs. 1); im Übrigen ( "Kostenfolgen in Dispositiv-Ziffer 3-5") bestätigte es das erstinstanzliche Urteil (Dispositiv-Ziff. 1 Abs. 2). Die Kosten des Berufungsverfahrens von Fr. 10'000.-- auferlegte das Kantonsgericht der Klägerin (Dispositiv-Ziff. 2), die es zudem zur Zahlung einer Parteientschädigung von Fr. 5'000.-- an den Beklagten verurteilte (Dispositiv-Ziff. 3). Das Kantonsgericht erwog, das Feststellungsinteresse sei eine Prozessvoraussetzung, die auch im Zeitpunkt des Entscheids noch bestehen müsse und von Amtes wegen zu prüfen sei. Die Klägerin habe ihr Feststellungsinteresse in sämtlichen Rechtsschriften mit einer aufgrund des Betreibungsregistereintrags eingeschränkten wirtschaftlichen Bewegungsfreiheit bzw. Kreditwürdigkeit begründet. Nachdem das Einsichtsrecht Dritter in den erwähnten Betreibungsregistereintrag nach Art. 8a Abs. 4 SchKG inzwischen infolge Zeitablaufs per 11. Juni 2014 weggefallen sei, könnte dieses nicht mehr zur Begründung eines im Berufungsverfahren aktuellen Feststellungsinteresses dienen. Entsprechend sei aufgrund des nachträglichen Wegfalls des Feststellungsinteresses (nach Ergehen des erstinstanzlichen Urteils) das Verfahren abzuschreiben. C. Mit Beschwerde in Zivilsachen beantragt der Beklagte dem Bundesgericht, es sei Dispositiv-Ziffer 1 Abs. 2 des Beschlusses des Kantonsgerichts Schwyz vom 29. Juni 2015 (recte: 22. Juni 2015) aufzuheben. Zudem seien Dispositiv-Ziffern 3 bis 5 des Urteils des Bezirksgerichts Höfe vom 21. Mai 2014 aufzuheben und die Kostenverlegung der Erstinstanz an die Vorinstanz zur Neuverlegung zurückzuweisen. Eventualiter seien die erstinstanzlichen Gerichtskosten der Beschwerdegegnerin aufzuerlegen, die zudem zu verpflichten sei, dem Beschwerdeführer die Parteikosten im festgesetzten Betrag zu ersetzen. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde. Die Vorinstanz hat auf eine Vernehmlassung verzichtet. Der Beschwerdeführer reichte dem Bundesgericht eine Replik, die Beschwerdegegnerin eine Duplik ein. D. Mit Verfügung vom 13. Oktober 2015 erteilte das Bundesgericht der Beschwerde die aufschiebende Wirkung.