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.