Sachverhalt:
A.
A.a. Die B._ AG (Klägerin, Beschwerdegegnerin) ist eine Aktiengesellschaft mit Sitz in U._. Sie bezweckt die Entwicklung, Planung, Projektierung und Realisierung von Bauten aller Art als Bau-, General- und Totalunternehmung.
Die A._ AG (Beklagte, Beschwerdeführerin) ist eine Aktiengesellschaft mit Sitz in V._. Sie bezweckt die Verlegung von Natursteinteppichen und Industriebodenbelägen sowie die Sanierung von Balkon- und Terrassenbelägen.
A.b. Am 21./28. Februar 2008 schlossen die Parteien einen "Pauschal-Werkvertrag" ab. Darin verpflichtete sich die A._ AG als Unternehmerin zur Erfüllung der "Arbeitsgattung BKP - 281.1 Fugenlose Bodenbeläge" für einen "Pauschalpreis inkl. MwSt." von Fr. 944'190.--. Gegenstand des Vertrags waren Bodenbeläge von über 16'000 m2 in zwei Gebäuden, bestehend aus rund 240 Zimmern sowie Gängen und Treppen.
A.c. Die Beschwerdeführerin verwendete bei den Arbeiten Materialien des Unternehmens C._ AG, hauptsächlich das Produkt "D._", eine Bodenbeschichtung auf Polyurethanbasis.
A.d. Nach Abschluss der Arbeiten stellte die A._ AG am 13. November 2008 die Schlussrechnung, die von der B._ AG beglichen wurde.
A.e. Wenige Monate später waren beim Bodenbelag stellenweise visuell gut sichtbare Schäden zu erkennen. Im Auftrag der B._ AG führte die E._ AG daraufhin eine materialtechnische Untersuchung und Beurteilung der Bodenbeläge durch. Der Untersuchungsbericht vom 30. Januar 2009 basiert auf 12 Untersuchungsstellen in verschiedenen Stockwerken beider Gebäude. Nach dem Bericht liegt die mittlere Stärke des Bodenbelags bei 1.05 mm.
A.f. In der Folge kam es zwischen den Parteien zu Gesprächen. Am 27. April 2009 fand eine gemeinsame Begehung vor Ort statt.
A.g. Mit Einschreiben vom 14. Mai 2009 setzte die B._ AG der A._ AG eine Frist bis zum 18. Mai 2009, um bestimmte Dokumente und Angaben zu liefern, namentlich einen "Massnahmenkatalog für die Beseitigung der Schäden" sowie eine "Offerte für die vorgeschlagenen Massnahmen".
A.h. Mit Einschreiben vom 11. Juni 2009 an die A._ AG rügte die B._ AG, dass der Boden mit durchschnittlich 1 mm statt 2-3 mm Dicke verlegt und dazu eine ungünstige Verfüllung mit Quarzsand vorgenommen worden sei, der Boden in dieser Qualität nicht brauchbar sei und die A._ AG trotz mehrmaliger Aufforderung keine Sanierungsmassnahmen vorgeschlagen habe. Sie setze ihr daher eine letzte Frist bis zum 19. Juni 2009 um konkrete Sanierungsmassnahmen, einen Zeitplan für die Umsetzung und die damit verbundenen Kosten zu unterbreiten. Sollte sie bis zu diesem Datum die genannten Elemente nicht oder nur teilweise erhalten, werde sie ein Drittunternehmen mit den Reparatur- bzw. Ersatzarbeiten beauftragen.
A.i. Mit Schreiben vom 19. Juni 2009 erklärte die A._ AG, sie habe die E._ AG mit einer neuen Schichtdickenmessung beauftragt, welche einen Durchschnittswert von 1.55 mm ergeben habe. Die Ursache der Schädigung könne auch bei einer unsorgfältigen Nutzung des Belags liegen; die Abklärungen betreffend Schadensursache würden laufen. Sie unterbreite der B._ AG folgenden Sanierungsvorschlag: Sie werde in den Schäden aufweisenden Zimmern eine zusätzliche Beschichtung und Versiegelung von ca. 1 mm auftragen, und zwar im Juli 2009 in 2-3 "Musterzimmern". Die "verbleibenden restlichen ca. 7 Zimmer" würden im Herbst 2009 saniert.
A.j. Der im Auftrag der A._ AG verfasste zweite Untersuchungsbericht der E._ AG vom 30. Juni 2009 basiert auf 61 Untersuchungsstellen in verschiedenen Stockwerken beider Gebäude und hält eine durchschnittliche Schichtdicke von 1.55 mm fest.
A.k. Im Juli 2009 nahm die A._ AG in drei Zimmern Nachbesserungsarbeiten vor.
A.l. Mit Einschreiben vom 25. März 2010 erklärte die B._ AG, die gesamten PU-Böden in beiden Gebäuden müssten nochmals neu gemacht werden. Es sei mit Sanierungskosten von rund Fr. 2 Mio. zu rechnen. Die A._ AG könne entweder ihrer Nachbesserungs- und Schadenersatzpflicht vollumfänglich nachkommen oder einen pauschalen Betrag von Fr. 400'000.-- per Saldo aller Ansprüche bezahlen.
A.m. Mit Einschreiben vom 30. März 2010 erklärte die A._ AG, sie habe mit Schreiben vom 19. Juni 2009 bereits einen Sanierungsvorschlag unterbreitet und gemäss diesem Vorschlag im Juli 2009 drei "Musterzimmer" mit einer Beschichtung und Versiegelung von zusätzlich ca. 1 mm überzogen. Die B._ AG habe seit Mitte Juli 2009 nicht mehr reagiert. Die A._ AG habe die Angelegenheit daher als erledigt betrachten dürfen. Sie schlage nun eine Besichtigung und Prüfung der drei "nachgebesserten" Böden sowie der übrigen Böden vor Ort vor, um den Nachbesserungsanspruch und den Umfang der allfälligen Nachbesserungspflicht zu prüfen.
A.n. Am 20. April 2010 fand eine gemeinsame Besichtigung der drei Musterzimmer statt.
A.o. Mit Schreiben vom 28. April 2010 teilte die B._ AG mit, sie habe sich entschlossen, ein Drittunternehmen mit der Einbringung eines neuen Bodens zu beauftragen. Mit Schreiben vom 28. November 2010 informierte die B._ AG die A._ AG darüber, dass die Sanierungsarbeiten in Ersatzvornahme ausgeführt worden seien und sich die Kosten dafür auf Fr. 2'109'655.50 beliefen. Sie forderte die A._ AG zur Zahlung dieses Betrags auf. Diese bestritt die Forderung und verweigerte die Zahlung.
B.
B.a. Am 20. Februar 2012 reichte die B._ AG beim Handelsgericht des Kantons Bern Klage ein und beantragte, die A._ AG sei zur Zahlung von Fr. 1 Mio. nebst Zins zu verurteilen.
B.b. Mit Verfügung vom 3. Juni 2013 beschränkte das Handelsgericht das Verfahren auf die Frage, ob die Voraussetzungen für eine Ersatzvornahme durch die B._ AG gegeben waren.
B.c. Mit Zwischenentscheid vom 18. September 2013 stellte das Handelsgericht des Kantons Bern fest, der B._ AG habe in Bezug auf das von der A._ AG gemäss Werkvertrag vom 21./28. Februar 2008 erstellte Werk ein Anspruch auf Ersatzvornahme zugestanden. Das Handelsgericht bejahte das Vorliegen eines Werkmangels (ungenügende Schichtdicke des Bodens, da unter 1.8 mm) und einer rechtzeitigen Mängelrüge, verneinte eine Genehmigung des Mangels und hielt fest, aufgrund der ausdrücklichen Verweigerung der Nachbesserung durch die A._ AG habe die B._ AG dieser keine Nachfrist zur Beseitigung des Mangels setzen müssen.
B.d. Gegen diesen Zwischenentscheid erhob die A._ AG Beschwerde in Zivilsachen beim Bundesgericht. Dieses hiess die Beschwerde mit Urteil 4A_511/2014 vom 4. März 2015 teilweise gut, soweit es darauf eintrat. Es hob den Zwischenentscheid des Handelsgerichts des Kantons Bern vom 18. September 2013 auf und wies die Sache zur Ergänzung des Sachverhalts und neuer Entscheidung an die Vorinstanz zurück.
Das Bundesgericht erwog, das Handelsgericht habe zu Recht einen Mangel und eine (inhaltlich genügende) Mängelrüge bejaht sowie eine Genehmigung des Werks durch die B._ AG verneint. Ob sich die A._ AG hingegen ausdrücklich geweigert hatte, eine Verbesserung am Werk vorzunehmen, liess sich aufgrund unvollständiger Sachverhaltsfeststellungen nicht beurteilen. Zudem bejahte das Bundesgericht eine Verletzung des rechtlichen Gehörs der A._ AG, weil sich das Handelsgericht nicht mit deren Einwand befasst hatte, die B._ AG habe anstatt einer Verbesserung des bestehenden Werks die Erstellung eines neuen Werks verlangt.
B.e. Mit Zwischenentscheid vom 19. Januar 2016 stellte das Handelsgericht des Kantons Bern (erneut) fest, der B._ AG habe in Bezug auf das von der A._ AG gemäss Werkvertrag vom 21./28. Februar 2008 erstellte Werk ein Anspruch auf Ersatzvornahme zugestanden. Das Handelsgericht kam zum Schluss, die A._ AG habe die verlangte vollständige Nachbesserung ausdrücklich verweigert, die Nachbesserungskosten seien nicht übermässig hoch und die B._ AG sei berechtigt gewesen, die Erstellung eines neuen Werks zu verlangen.
C.
Mit Beschwerde in Zivilsachen vom 10. März 2016 beantragt die A._ AG dem Bundesgericht sinngemäss, der Zwischenentscheid des Handelsgerichts des Kantons Bern sei aufzuheben und die Klage der B._ AG sei abzuweisen; eventualiter sei die Sache zur ergänzenden Abklärung und neuem Entscheid an das Handelsgericht zurückzuweisen.
Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten ist. Die Vorinstanz hat auf Vernehmlassung verzichtet.
Die Parteien haben repliziert und dupliziert.

Erwägungen:
1.
Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-ruling> E. 1 S. 133 mit Hinweisen).
1.1. Ist wie vorliegend ein selbständig eröffneter Vor- oder Zwischenentscheid angefochten, der weder die Zuständigkeit noch den Ausstand betrifft (<ref-law>), so ist die Beschwerde in Zivilsachen nach <ref-law> nur zulässig, wenn der Entscheid einen nicht wieder gutzumachenden Nachteil bewirken kann (lit. a) oder wenn die Gutheissung der Beschwerde sofort einen Endentscheid herbeiführen und damit einen bedeutenden Aufwand an Zeit oder Kosten für ein weitläufiges Beweisverfahren ersparen würde (lit. b). Es obliegt der Beschwerdeführerin, darzutun, dass die Voraussetzungen von <ref-law> erfüllt sind, soweit deren Vorliegen nicht offensichtlich in die Augen springt (<ref-ruling> E. 1.2 S. 47 mit Verweisen).
1.2. Die Beschwerdeführerin bringt zutreffend vor, dass mit der Gutheissung der Beschwerde sofort ein Endentscheid herbeigeführt werden könnte, da die Klage abzuweisen wäre, wenn das Vorliegen der Voraussetzungen für eine Ersatzvornahme verneint würde. Sie macht zudem geltend, dadurch würde ein erheblicher Zeit- und Kostenaufwand erspart, der mit der Durchführung eines Beweisverfahrens zur Frage der Höhe der Nachbesserungskosten verbunden wäre. Sie habe diesbezüglich u.a. eine Kostenexpertise beantragt, mit welcher zweifellos ein erheblicher Zeit- und Kostenaufwand verbunden sei.
1.3. Das Bundesgericht kam bereits in seinem Urteil 4A_511/2014 vom 4. März 2015 zum Schluss, aufgrund der Komplexität einer Kostenexpertise (Bodenbeläge von über 16'000 m2 in zwei Gebäuden, bestehend aus rund 240 Zimmern sowie Gängen und Treppen) zusammen mit weiteren Beweismassnahmen sei von einem Beweisverfahren auszugehen, das den üblichen Umfang übersteige. Gestützt auf diese Beurteilung ist die Voraussetzung von <ref-law> auch im vorliegenden Verfahren erfüllt und die Beschwerde gegen den angefochtenen Entscheid insoweit zulässig.
1.4. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde unter Vorbehalt rechtsgenüglicher Begründung (Art. 42 Abs. 2 i.V.m. <ref-law>; vgl. E. 2) einzutreten.
2.
2.1. Mit Beschwerde in Zivilsachen können Rechtsverletzungen gemäss Art. 95 und 96 BGG gerügt werden. Gemäss <ref-law> hat die Rechtsschrift die Begehren und deren Begründung zu enthalten; im Rahmen der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>), andernfalls wird darauf nicht eingetreten. Unerlässlich ist im Hinblick auf <ref-law>, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Verletzung von Bundesrecht liegt. Die Beschwerdeführerin soll dabei mit ihrer Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (vgl. <ref-ruling> E. 2.1 S. 245 f.).
2.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 2 S. 117, 264 E. 2.3 S. 266; <ref-ruling> E. 1.5). Entsprechende Rügen sind überdies bloss zulässig, wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Die Partei, welche die Sachverhaltsfeststellung der Vorinstanz anfechten will, muss klar und substanziiert aufzeigen, inwiefern diese Voraussetzungen erfüllt sein sollen (<ref-ruling> E. 1.3.1 S. 18, 264 E. 2.3 S. 266 mit Hinweisen). Die beschwerdeführende Partei soll in der Beschwerdeschrift zudem nicht bloss die Rechtsstandpunkte, die sie im kantonalen Verfahren eingenommen hat, erneut bekräftigen, sondern mit ihrer Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (<ref-ruling> E. 2 S. 89, 115 E. 2 S. 116). Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (<ref-ruling> E. 1.4.3 S. 255).
Zu beachten ist, dass das Bundesgericht in die Beweiswürdigung des Sachgerichts nur eingreift, wenn diese willkürlich ist. Willkür liegt nicht schon dann vor, wenn eine andere Lösung ebenfalls in Betracht zu ziehen oder gar vorzuziehen wäre, sondern nur, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 5.1 S. 22; <ref-ruling> E. 4.1 S. 133; <ref-ruling> E. 2.1 S. 211). Dass die von Sachgerichten gezogenen Schlüsse nicht mit der eigenen Darstellung der Beschwerdeführerin übereinstimmen, belegt keine Willkür (<ref-ruling> E. 2.3 S. 266 mit Verweisen).
3.
Die Vorinstanz kam in ihrem Zwischenentscheid zum Schluss, die Beschwerdeführerin habe sich ausdrücklich geweigert, eine Nachbesserung vorzunehmen, weshalb die Beschwerdegegnerin gestützt auf Art. 169 Abs. 2 SIA-Norm 118 zur Ersatzvornahme (vgl. Art. 169 Abs. 1 Ziff. 1 SIA-Norm 118) berechtigt gewesen sei. Nach Ansicht der Beschwerdeführerin hat die Vorinstanz die Voraussetzungen von Art. 169 Abs. 2 SIA-Norm 118 zu Unrecht bejaht.
3.1. Nach Art. 169 Abs. 1 SIA-Norm 118 hat der Bauherr bei jedem Mangel zunächst einzig das Recht, vom Unternehmer die Beseitigung des Mangels innerhalb angemessener Frist zu verlangen. Soweit der Unternehmer Mängel innerhalb der vom Bauherrn angesetzten Frist nicht behebt, ist der Bauherr berechtigt, nach seiner Wahl entweder weiterhin auf der Verbesserung zu beharren (Ziff. 1), einen dem Minderwert des Werkes entsprechenden Abzug von der Vergütung zu machen (Ziff. 2) oder vom Vertrag zurückzutreten (Ziff. 3). Hat sich der Unternehmer ausdrücklich geweigert, eine Verbesserung vorzunehmen, oder ist er hiezu offensichtlich nicht imstande, so stehen dem Bauherrn nach Art. 169 Abs. 2 SIA-Norm 118 die in Abs. 1 vorgesehenen Mängelrechte schon vor Ablauf der Verbesserungsfrist zu.
3.2. Die Beschwerdeführerin rügt zunächst, sie habe sich entgegen der Ansicht der Vorinstanz nicht i.S.v. Art. 169 Abs. 2 SIA-Norm 118 ausdrücklich geweigert, eine Verbesserung am Werk vorzunehmen.
3.2.1. Die Vorinstanz hat ausgeführt, die Beschwerdeführerin habe mit ihrem Schreiben vom 19. Juni 2009 mindestens sinngemäss bestritten, dass der gesamte PU-Boden an einem Werkmangel leide. Nach ihrer Nachbesserung in 2-3 "Musterzimmern" habe sie sich nicht mehr bei der Beschwerdegegnerin gemeldet. Die Beschwerdegegnerin habe aber eine Kontaktnahme erwarten dürfen, da die Beschwerdeführerin eine solche mit Hinweis auf laufende Abklärungen in Aussicht gestellt habe. Nachdem sich die Beschwerdegegnerin mit Einschreiben vom 25. März 2010 erneut an die Beschwerdeführerin gewandt habe, habe diese eine Besichtigung zum Zweck der Prüfung einer allfälligen Nachbesserungspflicht verlangt. Gleichzeitig habe sie aber erklärt, es sei nicht korrekt, dass die Parteien eine Mindestschichtstärke des PU-Bodens von 2-3 mm vereinbart hätten; zudem werde bei rund einem Drittel der Messpunkte der Mittelwert von 1.6 mm erreicht bzw. teilweise erheblich überschritten. Die Reaktion der Beschwerdeführerin sei mithin mehrdeutig ausgefallen: Zum einen habe sie eine Haftung für Werkmängel scheinbar nicht ausgeschlossen, zum andern habe sie das Vorliegen eines Werkmangels grösstenteils bestritten.
Entscheidend seien aber die Ergebnisse der gemeinsamen Besichtigung vom 20. April 2010. Anlässlich der Besichtigung der drei nachgebesserten Musterzimmer habe die Beschwerdeführerin (gemäss Schreiben der Beschwerdegegnerin vom 28. April 2010) dezidiert die Auffassung vertreten, die Schäden, welche der PU-Boden aufweisen würden, seien nicht von ihr zu vertreten bzw. könnten (soweit überhaupt erforderlich) mittels Neuauftragen einer ca. 1 mm PU-Schicht behoben werden. Mit dieser Aussage habe die Beschwerdeführerin ihre Haftung endgültig verneint. Zwar habe die Beschwerdeführerin offenbar hinzugefügt, "bzw." die Schäden könnten mittels Neuauftragen einer PU-Schicht behoben werden, so dass sich fragen könnte, wie dieses "bzw." zu verstehen sei. Es gelte aber zu bedenken, dass es kein Wortprotokoll der Besichtigung vom 20. April 2010 gebe. Aktenkundig sei bloss die nachträgliche Zusammenfassung der Haltung der Beschwerdeführerin. Ihre Aussage gemäss Protokoll sei daher schwerpunktmässig zu lesen. Der Schwerpunkt habe dabei in der Erklärung gelegen, die Beschwerdeführerin habe die Schäden nicht zu vertreten. Dass sie offenbar noch etwas hinzugefügt habe, zeige bloss, dass ihre Bereitschaft höchstens darin bestanden habe, sichtbare Beschädigungen am Boden nachzubessern, nicht aber den eigentlichen Werkmangel, die ungenügende Schichtdicke des gesamten PU-Bodens. Der Zusatz "soweit überhaupt erforderlich" lasse schliesslich darauf schliessen, dass die Beschwerdeführerin nicht vom Vorliegen eines Werkmangels ausgegangen sei, sondern diesen vielmehr bestritten habe.
Insgesamt sei festzustellen, dass die Beschwerdeführerin einen Werkmangel mehrfach bestritten habe. Auch im Verfahren vor Handels- und Bundesgericht habe die Beschwerdeführerin die Mangelhaftigkeit des Werks stets bestritten. Sie habe allein die sichtbaren Beschädigungen anerkannt und allenfalls Bereitschaft gezeigt, diese zu sanieren. Daneben habe die Beschwerdeführerin ihre Haftung aber endgültig verneint. Sie habe die von der Beschwerdegegnerin anbegehrte Nachbesserung der ungenügenden Schichtstärke der PU-Böden in 240 Zimmern sowie Gängen und Treppen nicht vornehmen wollen. Damit liege eine ausdrückliche Weigerung seitens der Beschwerdeführerin vor, die verlangte vollständige Nachbesserung vorzunehmen.
3.2.2. Nach Ansicht der Beschwerdeführerin ist es offensichtlich unhaltbar, wenn die Vorinstanz ihr wiederum vorwerfe, sie habe sich nach den Nachbesserungsarbeiten im Juli 2009 nicht mehr bei der Beschwerdegegnerin gemeldet; das Bundesgericht habe festgehalten, alleine gestützt auf die der Beschwerdeführerin vorgeworfenen Unterlassungen könne keine ausdrückliche Weigerung bejaht werden. Es bestehe keine Pflicht des Unternehmers, ein Angebot zu unterbreiten. Mit ihrem Schreiben vom 30. März 2010 habe sie weiter lediglich eine vereinbarte Schichtstärke von 2-3 mm bestritten. Eine Bestreitung der Haftung und des Mangels könne daraus nicht abgeleitet werden. Das Verhalten im Prozess sei nicht zu berücksichtigen, da eine ausdrückliche Weigerung im Zeitpunkt bestehen müsse, in welchem sich die Frage der Fristansetzung und der Ersatzvornahme stelle.
In Bezug auf die Besprechung der Parteien am 20. April 2010 vor Ort habe die Vorinstanz willkürlich auf das Schreiben der Beschwerdegegnerin vom 28. April 2010 abgestellt, wonach die Beschwerdeführerin anlässlich der gemeinsamen Besichtigung dezidiert eine Haftung abgelehnt habe. Dies sei eine reine Parteibehauptung, die von keinem der befragten Zeugen bestätigt worden sei und die zudem nicht einmal Eingang in die Rechtsschriften der Beschwerdegegnerin gefunden habe, weshalb auch eine Verletzung der Verhandlungsmaxime vorliege. Im Gegenteil habe die Beschwerdegegnerin im vorinstanzlichen Verfahren behauptet, die Beschwerdeführerin habe die Nachbesserung verweigert, indem sie innert einer mit Schreiben vom 28. April 2010 gesetzten Nachfrist von sechs Wochen nicht reagiert habe. Die Beschwerdegegnerin sei mithin selbst davon ausgegangen, dass vor diesem Schreiben - und damit auch an der Besichtigung vom 20. April 2010 - noch keine ausdrückliche Weigerung durch die Beschwerdeführerin vorgelegen habe. Es sei zudem widersprüchlich, wenn die Vorinstanz zunächst ausführe, es bestehe kein Wortprotokoll, sodann indessen selbst den Begriff Protokoll verwende.
Das Ergebnis der Besichtigung sei entgegen den vorinstanzlichen Feststellungen vielmehr gewesen, dass sich die Beschwerdegegnerin bezüglich des weiteren Vorgehens melden werde. Dies habe der Geschäftsführer der Beschwerdeführerin, F._, ausgesagt. Die Vorinstanz habe das rechtliche Gehör der Beschwerdeführerin verletzt und den Sachverhalt offensichtlich unrichtig und unvollständig festgestellt, indem sie dies nicht berücksichtigt habe. Die Beschwerdegegnerin habe im Zeitpunkt der Besichtigung bereits eine andere Lösung vor Augen gehabt, habe doch der Zeuge G._ (Mitarbeiter der Beschwerdegegnerin) ausgesagt, sie hätten parallele Lösungen entwickelt und im Februar 2010 "die Lösung zusammen gehabt". Zudem sei bei der Besichtigung der unsachgemässe Gebrauch des Bodens ein grosses Diskussionsthema gewesen. Die Nachbesserung habe die Beschwerdeführerin nie verweigert.
3.2.3. Entgegen der Ansicht der Beschwerdeführerin hat die Vorinstanz kein Bundesrecht verletzt, indem sie das Unterlassen einer Rückmeldung an die Beschwerdegegnerin berücksichtigt hat. Es trifft zwar zu, dass das Bundesgericht im Urteil 4A_511/2014 ausgeführt hat, alleine gestützt auf die der Beschwerdeführerin vorgeworfenen "Unterlassungen" könne eine ausdrückliche Weigerung nicht bejaht werden. Diese Formulierung zeigt aber gerade, dass die Unterlassungen zusammen mit anderen Sachverhaltselementen eine ausdrückliche Weigerung zu begründen vermögen, mithin ein weiteres Indiz für diese darstellen können. Wie im Übrigen das Schreiben der Beschwerdeführerin vom 30. März 2010 auszulegen ist und ob ihr Verhalten im Prozess berücksichtigt werden darf, kann offenbleiben. Denn die Vorinstanz ging zu Recht davon aus, entscheidend für die Frage einer Weigerung durch die Beschwerdeführerin seien die Ergebnisse der gemeinsamen Besichtigung vom 20. April 2010 (vgl. bereits Urteil 4A_511/2014 vom 4. März 2015 E. 5.4.3).
Bei der Würdigung das Verhaltens der Parteien an dieser Besichtigung hat die Vorinstanz nicht bloss auf Parteibehauptungen der Beschwerdegegnerin abgestellt. Vielmehr stellt das Schreiben der Beschwerdegegnerin vom 28. April 2010 eine Urkunde i.S.v. <ref-law> und damit ein Beweismittel dar (<ref-law>). Dieses Beweismittel konnte die Vorinstanz frei würdigen (vgl. <ref-law>) und durfte dabei auch berücksichtigen, dass das Schreiben von der Beschwerdegegnerin verfasst worden ist. Gemäss den verbindlichen Feststellungen des Prozesssachverhalts hat die Beschwerdegegnerin im vorinstanzlichen Verfahren behauptet, die Beschwerdeführerin habe ihre Nachbesserungspflicht (auch) anlässlich der Besichtigung vom 20. April 2010 bestritten. Die Vorinstanz hat somit nicht gegen die Verhandlungsmaxime verstossen, indem sie für diese Frage relevante Aussagen im Schreiben vom 28. April 2010 in ihre Sachverhaltsfeststellungen einbezog. Die Beschwerdeführerin bestreitet zu Recht nicht, dass eine ausdrückliche Weigerung vorliegt, wenn sie die im Schreiben vom 28. April 2010 zusammengefassten Aussagen so gemacht hat. Sie bestreitet aber die Richtigkeit des Inhalts dieses Schreibens. Dass die Vorinstanz trotzdem auf dieses durch die Beschwerdegegnerin verfasste Schreiben abgestellt hat, ist vertretbar und stellt damit keine willkürliche Beweiswürdigung dar. Eine solche lässt sich auch nicht aus dem Gebrauch des Wortes "Protokoll" ableiten; immerhin führte die Vorinstanz selbst ausdrücklich aus, es liege kein Wortprotokoll vor, sondern eine nachträgliche Zusammenfassung. Ob die Parteien sich bei der Besichtigung auch über den unsachgemässen Gebrauch des Bodens unterhalten hat, ist irrelevant. Soweit die Beschwerdeführerin zudem vorbringt, die Beschwerdegegnerin hätte spätestens im Zeitpunkt der Besichtigung bereits eine andere Lösung vor Augen gehabt, übersieht sie die verbindliche Sachverhaltsfeststellung der Vorinstanz, wonach die Beschwerdegegnerin auch im April 2010 eine Nachbesserung der Beschwerdeführerin noch angenommen hätte (vgl. bereits Urteil 4A_511/2014 vom 4. März 2015 E. 5.4.3).
Vor diesem Hintergrund ändert es nichts an der Beurteilung, dass die Beschwerdegegnerin am Ende der Besichtigung in Aussicht gestellt hat, sie werde sich melden. Dies war entgegen der Ansicht der Beschwerdeführerin nicht das - einzige - Ergebnis der Besichtigung, sondern vielmehr die Folge der Verweigerung einer Nachbesserung durch die Beschwerdeführerin. Die Vorinstanz hat im Übrigen in E. 38 durchaus festgestellt, dass der Geschäftsführer der Beschwerdeführerin ausgesagt hat, sie würden dann von der Beschwerdegegnerin hören. Eine Verletzung des rechtlichen Gehörs der Beschwerdeführerin liegt nicht vor. Die Vorinstanz hat somit kein Bundesrecht verletzt, indem sie zum Schluss kam, die Beschwerdeführerin habe bei der gemeinsamen Besichtigung am 20. April 2010 die verlangte vollständige Nachbesserung ausdrücklich verweigert.
3.3. Die Beschwerdeführerin bringt weiter vor, die Beschwerdegegnerin hätte ihr in jedem Fall eine Nachfrist ansetzen müssen. Art. 169 Abs. 2 SIA-Norm 118 sei mithin selbst bei einer Weigerung zur Nachbesserung nur erfüllt, wenn vor dieser Weigerung eine Nachfrist angesetzt worden sei. Die Vorinstanz habe dieses - bereits im vorinstanzlichen Verfahren vorgebrachte - Argument mit keinem Wort gewürdigt und damit nicht nur Art. 169 Abs. 2 SIA-Norm 118, sondern auch das rechtliche Gehör der Beschwerdeführerin verletzt.
Die Vorinstanz hat in E. 53.2 ausgeführt, die Berechtigung zur Ersatzvornahme könne sich ausnahmsweise auch ohne Ansetzung einer Verbesserungsfrist ergeben. Dies sei etwa der Fall, wenn sich die Unternehmerin ausdrücklich weigere, eine Verbesserung vorzunehmen. Da sie eine ausdrückliche Weigerung durch die Beschwerdeführerin bejahte, liess die Vorinstanz in E. 56 denn auch die Frage, ob die Beschwerdegegnerin eine angemessene Frist zur Verbesserung gesetzt habe, ausdrücklich offen. Damit hat die Vorinstanz zur von der Beschwerdeführerin aufgeworfenen Frage Stellung genommen. Die rechtlichen Ausführungen sind zudem korrekt (vgl. [so bereits die Vorinstanz] PETER GAUCH, Der Werkvertrag, 5. Aufl. 2011, N. 2667; ders., Kommentar zur SIA-Norm 118, Art. 157-190, 1991, N. 34 zu Art. 169 SIA-Norm 118). Die Rügen sind somit unbegründet.
3.4. Die Beschwerdeführerin rügt weiter, die Vorinstanz habe die Zulässigkeit der Erstellung eines neuen Werks zu Unrecht ausnahmsweise bejaht.
3.4.1. Grundsätzlich hat der Besteller kein Recht auf Neuherstellung des mangelhaften Werkes. Dieser Grundsatz gilt freilich nicht ohne Ausnahme: Ist die Nachbesserung aus sachlichen Gründen unmöglich, die Neuherstellung eines mangelfreien Werkes aber möglich, so hat der Besteller das Recht, vom Unternehmer die mögliche Neuherstellung anstatt der unmöglichen Nachbesserung zu verlangen. Einerseits ist zu berücksichtigen, dass der Besteller mit dem Abschluss des Werkvertrages Anspruch auf ein mangelfreies Werk erhält. Wenn das Ziel eines mangelfreien Werkes nur durch Neuherstellung erreicht werden kann, ist diese geschuldet. Andererseits fällt in Betracht, dass eine umfangreiche Nachbesserung bei weitreichenden Mängeln einer Neuherstellung des Werkes nahe kommen oder sogar gleich gestellt sein kann. Auch wenn der Besteller im Rahmen der Nachbesserung ausnahmsweise berechtigt ist, die Neuherstellung des Werkes zu verlangen, bleibt der Unternehmer indessen dadurch geschützt, dass die Neuherstellung nur verlangt werden kann, wenn dadurch nicht übermässige Kosten verursacht werden (Art. 169 Abs. 1 Ziff. 1 SIA-Norm 118, <ref-law>). Die Herstellung eines neuen Werkes kann somit verweigert werden, wenn diese im Verhältnis zum Nutzen des Bestellers übermässige Kosten verursacht (zum Ganzen: Urteil 4C.258/2001 vom 5. September 2002 E. 4.1.4 mit Hinweisen, nicht publ. in: <ref-ruling>).
3.4.2. Die Vorinstanz hat ausgeführt, die bei der Ersatzvornahme verlegten Linoleumböden stellten ein neues Werk dar. Das ursprünglich verwendete Produkt sei zwar nach wie vor zur Verfügung gestanden und hätte für ein Retopping verwendet werden können. Ein Retopping wäre dabei eine mögliche Variante einer Sanierung, wenn keiner oder feiner Quarzsand verwendet worden sei, namentlich bei Sanierungen, die ästhetische Probleme lösen sollten (im Sinne einer Unterhaltsmassnahme). Hier gehe es aber um eine Nachbesserung von über 16'000 m2 Boden, der zu 80 % eine ungenügende Schichtstärke (unter 1.8 mm) aufweise. Gegenstand der Nachbesserung sei somit nicht eine ästhetische, sondern eine funktionale Sanierung. Hier stelle ein blosses Retopping keine taugliche Nachbesserung dar. Eine ähnliche Beurteilung habe auch der Zeuge H._ vorgenommen, ein ausgebildeter Bauingenieur der ETH und (vor seiner Pensionierung) Abteilungsleiter bei der E._ AG. Er habe bei seiner Befragung ausgesagt:
"Es ist schwierig zu sagen, ob der Boden mit einem Retopping verbessert werden kann. Der Boden müsste ja neu angeschliffen oder ganz entfernt werden, um wieder einen Verbund zu bekommen. Hier mit den Quarzkörnern ist die Gefahr, dass der Boden beim Anschleifen ausreisst. Bei einem genügend dicken Belag könnte man sicher anschleifen und etwas drauf tun. Hier hätte ich eher etwas Bedenken, ob man damit eine dauerhafte Lösung gefunden hätte. Aber dazu haben wir keine Untersuchungen gemacht, ich sage das einfach aus Erfahrung. (...) Man hätte alles nochmal herausnehmen müssen und neu machen, um eine wirklich dauerhafte Lösung zu haben."
Der Zeuge I._, Projektleiter der C._ AG, und der Zeuge J._, ausgebildeter Bauingenieur HTL und Geschäftsleiter der C._ AG, hätten sich zwar weniger kritisch geäussert. Der Zeuge I._ habe ein Retopping als taugliche Sanierung eingeschätzt, wenn der Untergrund entsprechend gut sei. Beide Zeugen würden aber zum einen für das Unternehmen C._ AG arbeiten, den Lieferanten des verwendeten Bodenprodukts. Im Verhältnis zwischen der Beschwerdeführerin und der C._ AG stehe die Haftung der letzteren zur Diskussion. Zum anderen hätten beide Zeugen nur allgemeine Aussagen gemacht und seien von einem intakten bestehenden Boden ausgegangen. Der Zeuge I._ habe seine Aussagen ausdrücklich nur auf ästhetische Sanierungen bezogen. Aus diesen Zeugenaussagen könne nicht abgeleitet werden, dass ein Retopping im vorliegenden Fall eine taugliche Nachbesserung sei. Hinzu kämen schliesslich zeitliche Schwierigkeiten mit den verlangten Austrocknungszeiten und logistische Probleme bei einem Retopping. Es sei davon auszugehen, dass die Beschwerdeführerin nicht in der Lage gewesen wäre, die entsprechende Verbesserung in 240 Zimmern sowie Gängen und Treppen zeitlich so vorzunehmen, dass der im Gebäude untergebrachte Schulbetrieb nicht massgeblich beeinträchtigt gewesen wäre. Für ein Retopping wäre ein halbes Jahr zu veranschlagen gewesen. Eine entsprechende Sanierung wäre deshalb für die Beschwerdegegnerin bzw. die Gebäudenutzer mit unzumutbaren logistischen Schwierigkeiten verbunden gewesen.
Für ein Retopping hätte nach dem Gesagten der ganze PU-Boden aus beiden Gebäuden teilweise entfernt, jedenfalls aber angeschliffen, eventuell neu grundiert und der neue PU-Boden gegossen werden müssen. Der vorhandene Werkmangel, die ungenügende Schichtdicke, sei somit nicht leicht zu beheben gewesen. Sachliche Gründe hätten für Linoleum gesprochen, da dieser einfach über den bestehenden PU-Boden und ohne grosse Vorarbeit habe eingebracht werden können. Die Vorbehandlung und Neuerstellung eines PU-Bodens hätte mehr Arbeit verursacht. Eine derart umfangreiche Nachbesserung wäre einer Neuherstellung des Werks nicht nur gleichgestellt gewesen, sondern sogar darüber hinausgegangen. Auch die Kosten für den Linoleum-Boden dürften tendenziell tiefer ausgefallen sein verglichen mit Kosten für ein Retopping. Das neue Werk sei somit die vernünftigste und zweckmässigste Lösung gewesen.
3.4.3. Die Beschwerdeführerin wirft der Vorinstanz eine willkürliche Beweiswürdigung vor. Die Zeugen I._ und J._ hätten ein Retopping als technisch möglich und tauglich eingeschätzt. Demgegenüber habe der Zeuge H._ selbst eingestanden, er könne seine Aussagen auf keine Untersuchungen stützen. Der Geschäftsführer der Beschwerdeführerin habe ausgesagt, in jenem Zimmer, in welchem das Retopping-Verfahren angewandt worden sei, seien bei der Besichtigung am 20. April 2010 keine Schäden auszumachen gewesen. Diese habe der Zeuge G._ (Mitarbeiter der Beschwerdegegnerin) bestätigt, habe er doch festgehalten, dass es in diesem nachgebesserten Zimmer keine Schäden mehr gehabt habe. Es sei zudem irrelevant, dass die beiden Zeugen bei der C._ AG angestellt seien. Beide hätten unter Wahrheitspflicht ausgesagt und keine Veranlassung gehabt, Unwahrheiten zu verbreiten. Der Zeuge I._ habe seine Aussage entgegen der Ansicht der Vorinstanz nicht auf ästhetische Sanierungen beschränkt, sondern Bezug auf den konkreten Boden genommen, den er inspiziert habe. Damit sei der Beweis der Tauglichkeit erbracht. Wenn die Vorinstanz ausführe, die Zeugen I._ und J._ hätten nicht erklärt, dass ein Retopping im vorliegenden Fall eine taugliche Nachbesserung wäre, so verkenne sie die Beweislastverteilung, sei doch die Beschwerdegegnerin für die Untauglichkeit der vorgeschlagenen Nachbesserung beweispflichtig.
Die Vorinstanz habe zudem ausser Acht gelassen, dass nicht nur ein Retopping möglich gewesen wäre, sondern auch der Aus- und Neueinbau des PU-Bodens. Den Erwägungen zu zeitlichen Schwierigkeiten und logistischen Problemen sei bereits deshalb nicht zu folgen, weil nach den Sachverhaltsfeststellungen die Beschwerdegegnerin eine Nachbesserung selbst im April 2010 noch angenommen hätte. Daraus folge, dass selbst die Beschwerdegegnerin eine Sanierung als zumutbar erachtet habe. Die logistischen Herausforderungen dürften zudem nicht dazu führen, dass der Unternehmerin die Nachbesserungsmöglichkeit versagt werde, andernfalls würde diese Möglichkeit bei Werken der vorliegenden Art jeglichen Inhalts entleert. Irrelevant sei weiter, ob die Erstellung eines neuen Werks mit kleinerem Aufwand verbunden und allenfalls die vernünftigste und zweckmässigste Lösung sei. Vorausgesetzt sei vielmehr, dass die Nachbesserung aus sachlichen (objektiven) Gründen unmöglich sei; dies sei nicht der Fall. Die Vorinstanz sei auf die Voraussetzung der objektiven Unmöglichkeit nicht eingegangen, was eine Gehörsverletzung und eine unrichtige Rechtsanwendung darstelle.
3.4.4. Entscheidend ist die Sachverhaltsfeststellung der Vorinstanz, wonach ein Retopping keine taugliche Nachbesserung der Böden gewesen wäre. Die Vorinstanz stützte sich bei ihrer Beweiswürdigung auf die Aussagen des Zeugen H._, während sie die Aussagen der Zeugen I._ und J._ relativierte: Einerseits bezüglich ihres Inhaltes, weil die Zeugen nur allgemeine Aussagen gemacht hätten, von einem intakten bestehenden Boden ausgegangen seien und der Zeuge I._ seine Aussagen ausdrücklich nur auf ästhetische Sanierungen bezogen habe; andererseits berücksichtigte die Vorinstanz, dass die Zeugen bei der C._ AG arbeiten, deren Haftung im Verhältnis zur Beschwerdeführerin allenfalls im Raum steht. Diese Beweiswürdigung ist vertretbar. Daran ändert nichts, dass anlässlich der Besichtigung am 20. April 2010 im Zimmer, das die Beschwerdeführerin im Juli 2009 mit dem Retopping-Verfahren nachgebessert hatte, keine Schäden sichtbar gewesen seien. Aus der Tatsache, dass ein nachgebessertes Zimmer nach weniger als einem Jahr keine neuen Schäden aufweist, muss nicht zwingend der Schluss gezogen werden, ein Retopping stelle für die gesamte Fläche eine dauerhafte, taugliche Lösung dar. Die Vorinstanz durfte somit die Beweise ohne Willkür dahingehend würdigen, dass ein Retopping keine taugliche Nachbesserung dargestellt hätte. Gelangt das Gericht in Würdigung der Beweise zur Feststellung, eine Tatsache sei bewiesen oder widerlegt, so wird die - von der Beschwerdeführerin aufgeworfene - Frage der Beweislastverteilung nach <ref-law> gegenstandslos (<ref-ruling> E. 6.1 S. 202; <ref-ruling> E. 3 S. 282 m.w.H.).
Nachdem feststeht, dass ein Retopping keine taugliche Nachbesserung dargestellt hätte, kann offenbleiben, ob die Vorinstanz bei ihrer Beurteilung auch zeitliche und logistische Schwierigkeiten einbeziehen durfte. Denn gestützt auf dieses Beweisergebnis hat die Vorinstanz bundesrechtskonform die Zulässigkeit der Erstellung eines neuen Werks bejaht. Kann nämlich das Ziel eines mangelfreien Werkes nur durch Neuherstellung erreicht werden, ist diese geschuldet (oben E. 3.4.1). Dabei sei angemerkt, dass auch ein Aus- und Neueinbau des PU-Bodens keine Nachbesserung darstellen würde, sondern genauso wie der Einbau des Linoleum-Bodens ein neues Werk. Zudem hat die Vorinstanz aufgezeigt, dass die Vorbehandlung und Neuerstellung eines PU-Bodens mehr Arbeit verursacht hätte als die durch die Beschwerdegegnerin gewählte Variante. Damit sind die Voraussetzungen für die Zulässigkeit eines neuen Werks erfüllt. Die Vorinstanz hat im Übrigen die Rechtsprechung zu diesen Voraussetzungen, namentlich zur Unmöglichkeit der Nachbesserung und deren Konkretisierung, korrekt wiedergegeben und hat sich damit im Rahmen ihrer Subsumption auseinandergesetzt. Von einer Verletzung des rechtlichen Gehörs kann keine Rede sein. Damit erweisen sich die Rügen im Zusammenhang mit der Zulässigkeit der Erstellung eines neuen Werks als unbegründet.
3.4.5. Was schliesslich die Angemessenheit der Kosten für die Ersatzvornahme in der behaupteten Höhe von Fr. 2.1 Mio. angeht, so beschränkt sich die Beschwerdeführerin darauf, diese erneut als übermässig zu kritisieren. Dabei geht sie in keiner Weise auf die Erwägungen der Vorinstanz zu dieser Frage ein. So hat die Vorinstanz etwa ausgeführt, die Beschwerdegegnerin übernehme Fr. 600'000.-- der Kosten, was zu berücksichtigen sei. Da sich die Beschwerdeführerin im Rahmen ihrer Rüge nicht mit dem vorinstanzlichen Entscheid auseinandersetzt, ist auf die Rüge nicht einzutreten.
4.
Nach dem Gesagten ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Bei diesem Verfahrensausgang wird die Beschwerdeführerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1, Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 12'000.-- werden der Beschwerdeführerin auferlegt.
3.
Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 14'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Handelsgericht des Kantons Bern schriftlich mitgeteilt.
Lausanne, 21. Juni 2016
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Die Gerichtsschreiberin: Marti-Schreier