Sachverhalt:
A.
Die B._ Ltd. (Beschwerdegegnerin) ist eine Aktiengesellschaft mit Sitz in U._ im Kanton Bern. Die Firma A._ (Beschwerdeführerin) ist eine "Partnership Firm" nach indischem Recht mit Sitz in V._. Beide Gesellschaften sind im Bereich der Zeitmessung und Resultatermittlung/-verarbeitung bei Sportwettkämpfen tätig.
Vom 3. bis am 14. Oktober 2010 fanden in Delhi die Commonwealth Games statt. Die B._ Ltd. sorgte bei diesem Anlass für die Zeitmessung und Resultatverarbeitung. Gemäss "Letter Agreement" vom 22. Oktober 2009 hatte die Firma A._ sie bei der Erfüllung ihrer Aufgaben zu unterstützen, insbesondere durch Personal, Logistik und Infrastruktur. Vor Eröffnung der Spiele leistete die B._ Ltd. der Firma A._ Zahlungen von insgesamt Fr. 5'215'625.--. Später entstand Streit über die Vergütung der Firma A._.
B.
B.a. Am 29. August 2012 erhob die B._ Ltd. beim Handelsgericht des Kantons Bern Klage gegen die Firma A._ sowie C._ und D._. Sie begehrte, die Beklagten seien unter Strafandrohung zu verpflichten, "über ihre Geschäftsführung im Zusammenhang mit dem Projekt Commonwealth Games 2010 in Delhi umfassend Rechenschaft abzulegen" (Klagebegehren 1 und 2), näher umschrieben in den Ziffern 1.1 und 1.2. Weiter seien die Beklagten solidarisch zu verpflichten, "einen 30 000 Franken übersteigenden Betrag" zuzüglich Zins zu bezahlen (Klagebegehren 3).
Die Klage wurde den Beklagten zur Beantwortung zugestellt. Diese machten diverse Eingaben, reichten aber keine in einer Amtssprache verfasste Klageantwort ein, auch nicht innert vom Handelsgericht angesetzter Nachfrist. Am 14. Juni 2016 fand die Hauptverhandlung statt. Die Beklagten erschienen nicht und wurden vom Gericht säumig erklärt. Das Handelsgericht beschränkte das Verfahren an der Verhandlung "auf den ersten Teil der Stufenklage (Rechenschaftsablage) ". Mit Entscheid vom selben Tag verurteilte es die Firma A._ im Sinne der Klage zur Rechenschaftsablegung innert drei Monaten. Auf die Klage gegen C._ und D._ trat es nicht ein. Dieser Entscheid wurde den Beklagten am 22. Dezember 2016 rechtshilfeweise zugestellt und blieb unangefochten.
B.b. Am 20. März 2017 gingen dem Handelsgericht von Seiten der Firma A._ umfangreiche Dokumente zu (Datum der Eingabe: 6. März 2017), später ein Begleitschreiben dazu datiert vom 20. März 2017. In weiteren Eingaben präzisierte die Firma A._, dass sie keine Widerklage erhoben habe, und bat das Handelsgericht, "die in zwei Kartons zugeschickten Dokumente im Namen der Gerechtigkeit zu akzeptieren". Das Handelsgericht gab der B._ Ltd. daraufhin Gelegenheit, sich zu den Eingaben der Firma A._ zu äussern und ihre Forderungsklage zu beziffern. Mit Eingabe vom 29. Januar 2018 bezifferte die B._ Ltd. ihr Rechtsbegehren auf Fr. 1'501'575.79 zuzüglich Zins.
Am 12. Februar 2018 teilte Rechtsanwalt James Bouzaglo dem Handelsgericht mit, dass die Firma A._ Zustellungsdomizil bei ihm auf seiner Kanzlei in Genf verzeichne.
Nachdem es ein (erneutes) Sistierungsgesuch der Firma A._ abgewiesen hatte, lud das Handelsgericht die Parteien auf den 29. Oktober 2018 zu einer Fortsetzungsverhandlung vor, mit Pflicht zum persönlichen Erscheinen. Mit Eingabe vom 29. September 2018 beanstandete die Firma A._, ihr sei bislang im Verfahren nicht die Gelegenheit eingeräumt worden, auf die Klage zu antworten. Das Gericht verfüge damit nicht über alle Elemente, um über den Fall zu entscheiden. Das Handelsgericht hielt an der Vorladung fest. An der Fortsetzungsverhandlung vom 29. Oktober 2018 wurde je eine Parteibefragung durchgeführt. Weitere Beweisanträge der Firma A._ wurden abgewiesen. Mit Urteil vom selben Tag verurteilte das Handelsgericht die Firma A._, der B._ Ltd. Fr. 1'501'575.79 zuzüglich Zins zu bezahlen. "Soweit weitergehend" wies es die Klage ab.
C.
Die Firma A._ verlangt mit Beschwerde in Zivilsachen, das Urteil des Handelsgerichts vom 29. Oktober 2018 sei aufzuheben und die Forderungsklage der B._ Ltd. sei abzuweisen. Eventualiter sei die Sache zur Neubeurteilung im Sinne der Erwägungen an die Vorinstanz zurückzuweisen. Weiter ersuchte die Firma A._ um Gewährung der unentgeltlichen Rechtspflege für das bundesgerichtliche Verfahren.
Mit Verfügung vom 16. Januar 2019 entschied das Bundesgericht, dass das Verfahren in deutscher Sprache geführt wird. Das Gesuch der Firma A._ um Gewährung der unentgeltlichen Rechtspflege für das bundesgerichtliche Verfahren wies es ab.
Die Vorinstanz verzichtete auf Vernehmlassung, unter Verweis auf die Begründung des angefochtenen Entscheids. Die B._ Ltd. stellte ein Gesuch um Sicherstellung einer allfälligen Parteientschädigung, welches das Bundesgericht mit Präsidialverfügung vom 15. Mai 2019 guthiess. Die Firma A._ leistete in der Folge die verlangte Sicherheit in der Höhe von Fr. 18'000.--. Die B._ Ltd. erstattete daraufhin Beschwerdeantwort mit dem Antrag in der Sache, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Die Parteien reichten Replik und Duplik ein.

Erwägungen:
1.
1.1. Das Handelsgericht ist Fachgericht für handelsrechtliche Streitigkeiten und damit einzige kantonale Instanz im Sinne von <ref-law>. Gegen seine Entscheide steht die Beschwerde in Zivilsachen offen, gemäss <ref-law> unabhängig vom Streitwert (<ref-ruling> E. 1.2; <ref-ruling> E. 1.1, 2 E. 1.2.2).
1.2. Bei Stufenklagen sind das Hilfsbegehren auf Information und der Hauptanspruch in der Weise objektiv gehäuft, dass über das Hilfsbegehren zuerst zu entscheiden ist. Nach Erteilung der Information und entsprechender Bezifferung kann über das Hauptbegehren entschieden werden. Der Entscheid über den Hilfsanspruch auf Auskunftserteilung ist ein Teilentscheid, gegen den nach <ref-law> die Beschwerde an das Bundesgericht zulässig ist (siehe Urteil 4A_269/2017 vom 20. Dezember 2017 E. 1.2 mit Hinweisen, nicht publ. in <ref-ruling>). Nachdem der Entscheid des Handelsgerichts vom 14. Juni 2016 unangefochten geblieben ist, bildet einzig der Entscheid vom 29. Oktober 2018 Gegenstand der vorliegenden Beschwerde. Dabei handelt es sich um einen Endentscheid (<ref-law>).
1.3. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde einzutreten, unter Vorbehalt zulässiger und hinlänglich begründeter Rügen (siehe Erwägung 2).
2.
2.1. Mit Beschwerde in Zivilsachen können Rechtsverletzungen nach Art. 95 und 96 BGG gerügt werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Mit Blick auf die Anforderungen an die Begründung einer Beschwerde (<ref-law>) behandelt es aber grundsätzlich nur die erhobenen Rügen. Es ist nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese im Beschwerdeverfahren nicht mehr vorgetragen werden (<ref-ruling> E. 2 S. 88 f. mit Hinweisen).
Die Beschwerde ist innert der Beschwerdefrist vollständig begründet einzureichen (vgl. <ref-law>). Die Replik darf nur zu Darlegungen verwendet werden, zu denen die Ausführungen in der Vernehmlassung eines anderen Verfahrensbeteiligten Anlass geben (<ref-ruling> E. 2.2). Soweit die Beschwerdeführerin dies missachtet und in der Replik neue Rügen erhebt, können diese nicht berücksichtigt werden.
2.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Dazu gehören sowohl die Feststellungen über den streitgegenständlichen Lebenssachverhalt als auch jene über den Ablauf des vor- und erstinstanzlichen Verfahrens, also die Feststellungen über den Prozesssachverhalt (<ref-ruling> E. 1.3.1 mit Hinweisen). Es kann die Sachverhaltsfeststellung nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 2 S. 117; <ref-ruling> E. 1.5). Neue Tatsachen und Beweismittel dürfen nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<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 mit Hinweisen). Wenn sie den Sachverhalt ergänzen will, hat sie zudem mit präzisen Aktenhinweisen darzulegen, dass sie entsprechende rechtsrelevante Tatsachen und taugliche Beweismittel bereits bei den Vorinstanzen prozesskonform eingebracht hat (<ref-ruling> E. 2 S. 90). Genügt die Kritik diesen Anforderungen nicht, können Vorbringen mit Bezug auf einen Sachverhalt, der vom angefochtenen Entscheid abweicht, nicht berücksichtigt werden (<ref-ruling> E. 1.3.1 S. 18).
Beide Parteien stellen in ihren Rechtsschriften an das Bundesgericht den Sachverhalt und die Prozessgeschichte eingehend aus eigener Sicht dar. Darauf kann nicht abgestellt werden, erheben sie doch keine substanziierten Sachverhaltsrügen im soeben beschriebenen Sinn. Es ist durchwegs von den tatsächlichen Feststellungen der Vorinstanz auszugehen, und die Parteien können in rechtlicher Hinsicht nicht gehört werden, soweit sie ihre Argumentation auf einen Sachverhalt stützen, der für das Bundesgericht nicht massgebend ist (siehe im Einzelnen insbesondere Erwägung 5).
3.
Streitgegenstand ist die Rückerstattung eines Teils der Zahlungen, welche die Beschwerdegegnerin der Beschwerdeführerin geleistet hat. Die Beschwerdegegnerin macht einen vertraglichen Rückforderungsanspruch geltend. Die Beschwerdeführerin vertritt dagegen die Auffassung, dass sie den ausgerichteten Betrag gestützt auf einen vertraglichen Vergütungsanspruch vollumfänglich behalten dürfe.
Das Handelsgericht erwog, die Beschwerdeführerin sollte für ihre Unterstützung eine Vergütung erhalten, deren zwei Komponenten gemäss unbestritten gebliebener Darstellung in der Klage wie folgt definiert worden seien:
- Pauschalhonorar von 3% des Bruttobarwerts des Vertrages zwischen der Beschwerdegegnerin und dem Organisationskomitee der Spiele.
- Auslagenersatz für den "direkten und indirekten Aufwand" bei der Projektabwicklung.
Welche Tatsachen die Beschwerdeführerin zu behaupten und zu beweisen habe, damit sie die Akontozahlungen ganz oder teilweise behalten könne (Durchsetzung des Vergütungsanspruchs als Gegenanspruch), sei "hier durch den (bereits) beurteilten Anspruch auf Rechenschaftsablegung definiert". Denn die Parteien hätten unbestrittenermassen vereinbart, dass der Entschädigungsanspruch erst nach Vorlage der konformen Schlussrechnung festgestellt werden könne. Die Schlussrechnung habe sich dabei über den "effektiven Aufwand" und die "effektiven Auslagen" zu äussern. Zudem seien nur Aufwand und Auslagen zu entschädigen, welche im Zuge der "Projektabwicklung" der Commonwealth Games 2010 angefallen seien.
In der Folge untersuchte das Handelsgericht die bestrittenen Positionen der Abrechnung im Einzelnen auf der Grundlage der Eingabe der Beschwerdeführerin vom 6. März 2017. Sie gelangte zum Fazit, der Beschwerdeführerin sei es misslungen, höhere Kosten nachzuweisen als jene, die von der Beschwerdegegnerin ganz oder teilweise anerkannt worden seien. Nach der getroffenen Parteivereinbarung habe die Beschwerdeführerin der Beschwerdegegnerin somit die Differenz zwischen Pauschalhonorar (Fr. 749'700.--) und Auslagen (Fr. 2'964'349.21) einerseits und den Akontozahlungen von Fr. 5'215'625.-- andererseits (zuzüglich Zins) zurückzuerstatten.
4.
Die Beschwerdeführerin kritisiert in prozessualer Hinsicht, das Handelsgericht habe wiederholt ihren Anspruch auf rechtliches Gehör verletzt.
Sie meint, das Handelsgericht habe ihrer Säumnis durch Nichterscheinen zur Hauptverhandlung vom 14. Juni 2016 eine falsche Tragweite zugemessen, zumal in dem anlässlich dieser Verhandlung ergangenen Entscheid lediglich der Hilfsanspruch der Beschwerdegegnerin auf Rechenschaftsablegung beurteilt worden sei. Dabei verkennt sie, dass die Beschränkung des Prozessthemas auf den Hilfsanspruch erst erfolgte, nachdem sie (die Beschwerdeführerin) bereits durch Nichteinreichen einer formgültigen Klageantwort und zufolge Nichterscheinens zur Hauptverhandlung vom 14. Juni 2016 bei den ersten Parteivorträgen säumig geworden war. Dass der Entscheid vom 14. Juni 2016 in der Tat lediglich den Hilfsanspruch auf Rechenschaftsablegung feststellte, hat entgegen der Beschwerdeführerin nicht zur Folge, dass das Verfahren mit Bezug auf das Hauptbegehren damit von Neuem begonnen hätte. Soweit die Beschwerdegegnerin ihren Forderungsanspruch in der Klage vom 29. August 2012 bereits substanziiert behauptet hatte, hat die Beschwerdeführerin ihr Recht auf Beantwortung durch ihre Säumnis verwirkt. Die Vorinstanz hat ihr somit zu Recht nicht noch einmal Gelegenheit zur umfassenden Beantwortung der Klage eingeräumt. Weshalb die Beschwerdeführerin - wie sie in der Replik geltend macht - berechtigt gewesen sein soll, an der Fortsetzungsverhandlung vom 29. Oktober 2018 die versäumte Klageantwort nachzuholen, ist nicht erkennbar. Die in der Beschwerde wiedergegebenen Ausführungen der Vorinstanz in ihrer Verfügung vom 9. Oktober 2018 sind nicht zu beanstanden.
Sodann erblickt die Beschwerdeführerin eine Gehörsverletzung darin, dass ihr das Handelsgericht verweigert habe, zur Klagebezifferung durch die Beschwerdegegnerin vom 29. Januar 2018 Stellung zu nehmen. Die Rüge geht fehl: Gemäss den für das Bundesgericht verbindlichen (Erwägung 2.2) Feststellungen der Vorinstanz wurde die Eingabe der Beschwerdegegnerin vom 29. Januar 2018 der Beschwerdeführerin mittels Publikation im Schweizerischen Handelsamtsblatt zugestellt, und es wurde ihr Frist angesetzt, um hierzu Stellung zu nehmen. Nach der Mitteilung des Zustellungsdomizils der Beschwerdeführerin liess der Instruktionsrichter Rechtsanwalt Bouzaglo ein Exemplar der Klage inklusive Beilagen und der Forderungsbezifferung zukommen. In der Folge liess sich die Beschwerdeführerin zur Forderungsbezifferung und den dortigen Bestreitungen nicht vernehmen. Unter diesen Umständen ist der Vorwurf der Beschwerdeführerin, sie habe sich vor dem Handelsgericht nicht zur Klagebezifferung äussern können, nicht nachvollziehbar.
Die behaupteten Verletzungen von <ref-law> sowie von Art. 53 Abs. 1 und Art. 222 ZPO liegen nicht vor.
5.
Die Beschwerdeführerin beanstandet eine offensichtlich unrichtige Feststellung diverser entscheiderheblicher Tatsachen. Sie begründet jedoch in der Folge keine gemäss den dargelegten Grundsätzen zulässige Sachverhaltsrüge, sondern schildert stattdessen in Missachtung von Art. 97 und Art. 105 BGG den Sachverhalt aus eigener Sicht, als ob das Bundesgericht eine Appellationsinstanz mit umfassender tatsächlicher Überprüfungsbefugnis wäre. Darauf ist nicht weiter einzugehen (siehe Erwägung 2.2).
Als willkürliche Beweiswürdigung kritisiert die Beschwerdeführerin ferner das Verständnis der Vorinstanz, wonach die Vergütung der Beschwerdeführerin aus zwei Komponenten bestehen sollte. Indessen würdigte die Vorinstanz in diesem Punkt nicht die Beweise, sondern sie stellte auf die unbestritten gebliebene Darstellung in der Klage ab. Die Beschwerdeführerin kann keine Willkür bei der Sachverhaltsfeststellung belegen, wenn sie dem unter Hinweis auf den Wortlaut des "Letter Agreement" vom 22. Oktober 2009 ihr eigenes Verständnis der vertraglichen Vereinbarungen gegenüberstellt, zumal sie dabei nach Belieben neue tatsächliche Behauptungen einbringt und aus diesen ihre eigenen Schlüsse auf den tatsächlichen Willen der Parteien zieht, so insbesondere, die Beschwerdegegnerin habe gewusst, dass der geschuldete Betrag jedenfalls nicht unter Fr. 8'953'814.-- liegen würde. Im Übrigen tut die Beschwerdeführerin auch nicht dar, weshalb das Handelsgericht hinsichtlich des Vertragsinhalts angesichts ihrer Säumnis im kantonalen Verfahren nicht auf die Darstellung in der Klage hätte abstellen dürfen. Damit braucht nicht erörtert zu werden, wie weit die Beschwerdeführerin überhaupt noch berechtigt ist, das vorinstanzliche Verständnis des "Letter Agreement" vom 22. Oktober 2009 in Frage zu stellen, nachdem sie den Entscheid des Handelsgerichts vom 14. Juni 2016 nicht angefochten hat, dem dieses bereits zugrunde lag (Erwägung 1.2).
Schliesslich rügt die Beschwerdeführerin in diesem Punkt eine Verletzung der Regeln der Vertragsauslegung (<ref-law>). Sie begründet jedoch eine solche nicht zulässig, indem sie behauptet, die Auslegung entspreche nicht dem übereinstimmenden tatsächlichen Willen der Parteien, ohne darzutun, dass ein solcher im angefochtenen Urteil festgestellt worden wäre oder hätte festgestellt werden müssen.
6.
Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend wird die Beschwerdeführerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG). Die Parteientschädigung ist aus der an die Bundesgerichtskasse geleisteten Sicherheit auszurichten.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 16'000.-- werden der Beschwerdeführerin auferlegt.
3.
Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 18'000.-- zu entschädigen. Diese Entschädigung wird aus der an die Bundesgerichtskasse bezahlten Sicherheitsleistung ausgerichtet.
4.
Dieses Urteil wird den Parteien und dem Handelsgericht des Kantons Bern schriftlich mitgeteilt.
Lausanne, 30. April 2020
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Kölz