Sachverhalt:
A.
Mit Zahlungsbefehl Nr. yyy des Betreibungsamtes Zürich 2 vom 10. November 2014 betrieb die B._ AG A._ über Fr. 4'893'413.80. A._ erhob Rechtsvorschlag.
Am 16. Dezember 2014 ersuchte die B._ AG das Bezirksgericht Zürich um Rechtsöffnung. Das Bezirksgericht erteilte am 15. Mai 2015 definitive Rechtsöffnung für Fr. 4'891'974.55 und provisorische Rechtsöffnung für Fr. 1'439.25. Den Antrag von A._ auf Löschung der Betreibung wies das Bezirksgericht ab.
B.
Am 12. Juni 2015 erhob A._ Beschwerde an das Obergericht des Kantons Zürich. Er verlangte, das Urteil des Bezirksgerichts vom 15. Mai 2015 aufzuheben und das Rechtsöffnungsgesuch abzuweisen. Zudem ersuchte er um aufschiebende Wirkung.
Das Obergericht wies das Gesuch um aufschiebende Wirkung am 14. September 2015 ab (vgl. dazu Verfügung 5A_741/2015 vom 18. April 2016).
Mit Urteil vom 24. Februar 2016 wies das Obergericht die Beschwerde ab, soweit es darauf eintrat.
C.
Am 18. April 2016 hat A._ (Beschwerdeführer) Beschwerde in Zivilsachen an das Bundesgericht erhoben. Er verlangt die Aufhebung des Urteils des Obergerichts vom 24. Februar 2016 und die Abweisung des Rechtsöffnungsgesuchs.
Am 21. April 2016 hat die B._ AG (Beschwerdegegnerin) beantragt, den Beschwerdeführer zur Sicherstellung der Parteientschädigung in angemessener Höhe, mindestens aber Fr. 20'000.--, zu verpflichten. Der Beschwerdeführer hat die Abweisung des Gesuchs beantragt. Mit Präsidialverfügung vom 9. Mai 2016 hat das Bundesgericht das Gesuch abgewiesen, da die Beschwerdegegnerin noch nicht zu einer Vernehmlassung aufgefordert worden war.
Das Bundesgericht hat die Akten beigezogen, in der Sache aber keine Vernehmlassungen eingeholt.

Erwägungen:
1.
1.1. Die vorliegende Beschwerde in Zivilsachen betrifft eine Schuldbetreibungssache und erweist sich grundsätzlich als zulässig (Art. 72 Abs. 2 lit. a, Art. 74 Abs. 1 lit. b, Art. 75, Art. 76, Art. 90, Art. 100 Abs. 1 i.V.m. Art. 46 Abs. 1 lit. a i.V.m. <ref-law>). Auf weitere Eintretensfragen ist im Sachzusammenhang einzugehen.
1.2. Der Beschwerdeführer verlangt die Aufhebung des angefochtenen Urteils. Gegenstand dieses Urteils war auch der ursprüngliche Antrag des Beschwerdeführers auf Löschung der Betreibung. Das Obergericht ist auf diesen Punkt nicht eingetreten, da der Beschwerdeführer keinen Antrag in der Sache gestellt hatte. Dies tut der Beschwerdeführer auch vor Bundesgericht nicht und er äussert sich auch sonst nicht dazu. Folglich ist davon auszugehen, dass dieser Punkt trotz des weitgefassten Aufhebungsantrags nicht Gegenstand der Beschwerde in Zivilsachen ist.
2.
2.1. Das vorliegende Rechtsöffnungsverfahren steht vor folgendem Hintergrund: Mit Berufungsentscheid vom 15. April 1997 verpflichtete das Obergericht des Kantons Zürich den Beschwerdeführer, an F._ Fr. 2'600'000.-- nebst Zins zu 12 3⁄4 % seit 1. Mai 1993 sowie Fr. 481'821.90 zu bezahlen. Die dem Verfahren zugrunde liegende Arrestbetreibung endete am 8. Februar 1999 in einem Verlustschein über Fr. 4'893'413.80. Die Beschwerdegegnerin stützt sich im Rechtsöffnungsverfahren auf das genannte Urteil vom 15. April 1997 und im Umfang der ursprünglichen Betreibungskosten auf den Verlustschein vom 8. Februar 1999. Beide Titel weisen F._ als Gläubigerin aus. Gemäss Eintrag im Handelsregister war sie bis im Oktober 1998 Mitglied des Verwaltungsrates der Beschwerdegegnerin (mit Einzelunterschrift). Zum Nachweis ihrer Rechtsnachfolge beruft sich die Beschwerdegegnerin auf eine Zession vom 3. Juli 2000.
Im Rechtsöffnungsverfahren bestritt der Beschwerdeführer, dass die dem Urteil vom 15. April 1997 zugrunde liegende Forderung rechtsgültig im Namen von F._ erstritten und der Verlustschein in ihrem Auftrag erwirkt worden war. Ebenso bestritt er die Rechtsgültigkeit der Zession vom 3. Juli 2000. Der Beschwerdeführer stützte sich vor allem auf eine notariell beglaubigte, schriftliche Erklärung von F._ vom 13. Januar 2015. Darin bestätigt sie, die Vollmacht zur Führung des vor Bezirksgericht Zürich geführten Verfahrens und des späteren Rechtsmittelverfahrens vor Zürcher Obergericht sei "offenbar erschlichen" und die Verfahren seien folglich ohne ihr Wissen geführt worden. Sodann sei die auf der Zession vom 3. Juli 2000 angebrachte Unterschrift "missbraucht und zweckentfremdet worden".
2.2.
2.2.1. Hinsichtlich der Zession hat das Obergericht die Tatsachenbehauptungen des Beschwerdeführers zunächst nicht als schlüssig erachtet. Zwar habe er geltend gemacht, die Zession sei genauso wenig gültig wie die Vollmacht und die Unterschriften seien gefälscht: Zuvor habe er aber ausgeführt, die Zession könne wie die Vollmacht vermutlich nur eine Fälschung sein. Später habe er erklärt, "dass Frau F._ in ganz einfachen Worten gesagt hat, dass sie entweder die Zession nicht unterzeichnet habe oder - für den Fall, dass sie die Zession unterzeichnet hat - dass die Unterschrift in einen Zusammenhang gesetzt worden sein könnte. Sie ist sich nicht zu 100 % sicher". Damit sei der Tatsachenvortrag - für sich alleine betrachtet wie auch im Zusammenhang mit der schriftlichen Erklärung von F._ vom 13. Januar 2015 - alles andere als schlüssig und damit nicht geeignet, an der Gültigkeit der Zession ernsthafte Zweifel zu wecken. Weitere Sachverhaltsabklärungen würden dadurch nicht veranlasst. Das Obergericht hat die Darstellung des Beschwerdeführers auch nicht als glaubhaft erachtet. Er habe zwar weiter geltend gemacht, der Kaufvertrag vom 6. Oktober 1998 (Kaufvertrag zwischen F._ und ihrem Sohn G._, vertreten durch den Vater E._, worin ein Kaufpreis von Fr. 3'500.-- für schlecht einbringliche Forderungen von Fr. 2'600'000.-- und Fr. 481'821.90 vereinbart worden sei) belege, dass E._ - der auch die Beschwerdegegnerin beherrsche - einen Weg gesucht habe, um die im Namen von F._ ohne ihr Wissen erstrittene Forderung gegen den Beschwerdeführer zu kontrollieren. Die Strafakten sollten gemäss dem Beschwerdeführer sodann belegen, dass E._ sowohl im Zivil- wie im Strafverfahren F._ mit allen Mitteln vollständig ausgeklammert habe; sie habe die Prozesse nur formal geführt. Nach der Einschätzung des Obergerichts sind diese Behauptungen und die dazu eingereichten Urkunden allenfalls gewisse Indizien für die Darstellung des Beschwerdeführers. Die durch sie erweckten Zweifel an der Gültigkeit der Zession seien jedoch nicht gewichtig genug, um diese Darstellung als wahrscheinlicher erscheinen zu lassen als die Authentizität der auf der Zession (bzw. Vollmacht) angebrachten Unterschrift von F._. Somit sei die behauptete Fälschung nicht glaubhaft und die Rechtsnachfolge liquide nachgewiesen.
Mangels hinreichender Beanstandung sei nicht zu prüfen, ob das Bezirksgericht zu Recht von einer Einvernahme von F._ als Zeugin abgesehen habe. Das Bezirksgericht habe rechtsgenügend begründet, weshalb ihre Zeugenaussage kein taugliches Beweismittel darstellen würde (nämlich damit, dass der vertiefte Kontakt zwischen dem Beschwerdeführer und F._ während des Rechtsöffnungsverfahrens ihre Unabhängigkeit und Glaubhaftigkeit als Zeugin erheblich beeinträchtige). Mit diesen Erwägungen des Bezirksgerichts habe sich der Beschwerdeführer in der kantonalen Beschwerde nicht auseinandergesetzt.
2.2.2. Ausserdem lägen keine objektiven Anhaltspunkte für eine gefälschte Vollmacht vor. F._ mache nicht geltend, sie habe Rechtsanwalt Dr. H._ keine Vollmacht erteilt, es handle sich um eine Fälschung. Sie spreche lediglich von einer offenbar erschlichenen Prozessvollmacht. Der Beschwerdeführer selber führe aus, dass die auf der Vollmacht angebrachte Unterschrift von F._ gefälscht bzw. zumindest als Blankounterschrift missbraucht oder zweckentfremdet worden sei. Aufgrund derart vager und widersprüchlicher Behauptungen habe das Bezirksgericht keine weiteren Sachverhaltsabklärungen vornehmen müssen. Wenn sich der Beschwerdeführer auf eine gefälschte Vollmacht berufen wolle, so wäre dies mit Revision anzustreben, soweit dies heute noch möglich sei.
2.3. Vor Bundesgericht beruft sich der Beschwerdeführer nur noch auf die Fälschung der Zession. Einzig zur Stützung dieses Standpunkts kommt er am Rande auf die angebliche Fälschung der seinerzeitigen Prozessvollmacht zurück.
2.3.1. Er wirft dem Obergericht vor, ein falsches Beweismass angewandt zu haben. Es habe faktisch mehr als blosse Glaubhaftmachung der Einwendungen verlangt, nämlich überwiegende Wahrscheinlichkeit.
Glaubhaft gemacht ist eine Tatsache dann, wenn für ihr Vorhandensein aufgrund objektiver Anhaltspunkte eine gewisse Wahrscheinlichkeit spricht, selbst wenn das Gericht noch mit der Möglichkeit rechnet, dass sie sich nicht verwirklicht haben könnte (<ref-ruling> E. 4.1.2 S. 144; <ref-ruling> E. 3.3 S. 325; <ref-ruling> E. 4c S. 398; <ref-ruling> E. 4 S. 413). Die Wahrscheinlichkeit muss im vorliegenden Zusammenhang in dem Sinne überwiegen, als mehr für die Verwirklichung der behaupteten, die Rechtsöffnung hindernden Tatsachen sprechen muss als dagegen (<ref-ruling> E. 4.1.2 S. 144; Urteile 5A_881/2011 vom 16. März 2012 E. 3.3, in: Pra 2012 Nr. 103 S. 712; 5A_113/2014 vom 8. Mai 2014 E. 3.1). Das Obergericht hat sich auf diese Rechtsprechung gestützt, als es die Authentizität der Unterschrift auf der Zessionsurkunde als wahrscheinlicher erachtet hat als die Darstellung des Beschwerdeführers. Eine Verletzung des Beweismasses ist demnach nicht ersichtlich. Die Einwände des Beschwerdeführers richten sich vielmehr gegen die Beweiswürdigung, die das Bundesgericht nur im Rahmen von <ref-law>, insbesondere auf Willkür hin, überprüfen kann (unten E. 2.3.3), und gegen die Beurteilung des Obergerichts, dass seine Behauptungen nicht schlüssig seien.
2.3.2. Hinsichtlich der Schlüssigkeit seiner Darstellung macht der Beschwerdeführer geltend, seine Behauptungen seien deutlich genug ausgefallen. Er habe klar eine Urkundenfälschung behauptet, wobei es keine Rolle spiele, ob die Urkundenfälschung durch Fälschung der Unterschrift oder das Verwenden der nicht gefälschten Unterschrift unter eine ohne Wissen und Willen von F._ erstellte Zessionserklärung zustande gekommen sei.
In der Tat würde sowohl die eine wie die andere Behauptung - so sie denn glaubhaft gemacht wäre - zur Abweisung des Rechtsöffnungsgesuchs führen. Wie dem angefochtenen Urteil zu entnehmen ist, scheinen die schwankenden Behauptungen des Beschwerdeführers darauf zurückzuführen zu sein, dass F._ selber nicht sicher ist, wie es sich tatsächlich verhält (vgl. oben E. 2.2.1). Es kann offen bleiben, wie solchen Unsicherheiten Rechnung zu tragen ist, um den Tatsachenvortrag nicht unschlüssig erscheinen zu lassen. Sie können jedenfalls im Rahmen der Beweiswürdigung berücksichtigt werden, und dies hat das Obergericht denn auch im Ergebnis getan, indem es die Fälschung der Unterschrift schliesslich als nicht glaubhaft erachtet hat. Die Frage ist deshalb im Rahmen der erhobenen Sachverhaltsrügen zu prüfen.
2.3.3. Diesbezüglich macht der Beschwerdeführer geltend, er habe die Urkundenfälschung glaubhaft gemacht, da die angebliche Zedentin erklärt habe, dass ihre Unterschrift zweckentfremdet und missbraucht worden sei und dass sie als eine nahe am Existenzminimum lebende Person niemals eine Forderung von Fr. 4'893'413.80 entschädigungslos an die Beschwerdegegnerin abgetreten hätte. Die Zession vom 3. Juli 2000 müsse im Zusammenhang mit dem Forderungsverkauf vom 6. Oktober 1998, den Strafakten von 1998/1999 und der Erklärung von F._ vom 13. Januar 2015 betrachtet werden. Das Obergericht habe die Erklärung von F._ im Zusammenhang mit der Zessionserklärung überhaupt nicht gewürdigt und sei dadurch in Willkür verfallen.
Der vorinstanzlich festgestellte Sachverhalt ist für das Bundesgericht grundsätzlich verbindlich (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn die Feststellung offensichtlich unrichtig - d.h. willkürlich (<ref-ruling> E. 1.5 S. 130 mit Hinweis) - ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und die Behebung des Mangels für den Verfahrensausgang entscheidend sein kann (<ref-law>). Will der Beschwerdeführer die Sachverhaltsfeststellungen der Vorinstanz anfechten, muss er darlegen, inwiefern die genannten Voraussetzungen erfüllt sein sollen (<ref-ruling> E. 4.2 S. 234; <ref-ruling> E. 5.1 S. 356). Bei der Rüge der offensichtlich unrichtigen Sachverhaltsfeststellung gilt das strenge Rügeprinzip (<ref-law>) und es ist demnach anhand der Erwägungen des angefochtenen Entscheids klar und detailliert darzulegen, inwiefern die vorinstanzliche Sachverhaltsfeststellung willkürlich sein soll. Demzufolge genügt es nicht, einen von den tatsächlichen Feststellungen der Vorinstanz abweichenden Sachverhalt zu behaupten. Auf solche rein appellatorische Kritik am Sachverhalt tritt das Bundesgericht nicht ein (<ref-ruling> E. 1.4.2 und 1.4.3 S. 254 f.; <ref-ruling> E. 2.2 S. 246; <ref-ruling> E. 5.1 S. 356).
Willkür liegt nicht schon dann vor, wenn eine andere Lösung ebenfalls in Betracht zu ziehen oder gar vorzuziehen wäre. Die Sachverhaltsfeststellung bzw. Beweiswürdigung erweist sich vielmehr erst dann als willkürlich, wenn das Gericht Sinn und Tragweite eines Beweismittels offensichtlich verkannt hat, wenn es ohne sachlichen Grund ein wichtiges und entscheidwesentliches Beweismittel unberücksichtigt gelassen oder wenn es auf der Grundlage der festgestellten Tatsachen unhaltbare Schlussfolgerungen gezogen hat. Dass die von Sachgerichten gezogenen Schlüsse nicht mit der eigenen Darstellung des Beschwerdeführers übereinstimmen, belegt keine Willkür (<ref-ruling> E. 2.3 S. 266; <ref-ruling> E. 3.1 S. 178; je mit Hinweisen).
Das Obergericht hat die Erklärung von F._ vom 13. Januar 2015 keineswegs übergangen, sondern im Zusammenhang mit der Schlüssigkeit des Tatsachenvortrags erwähnt. Ob das Obergericht ihre Erklärung dabei wie ein Beweismittel oder wie eine Parteibehauptung behandelt hat, ist nicht klar, kann aber offen bleiben, da es sie so oder anders offenbar als wenig aussagekräftig beurteilt hat. Im Übrigen verweist der Beschwerdeführer zwar auf verschiedene Umstände (insbesondere im Zusammenhang mit dem Kaufvertrag vom 6. Oktober 1998 und den Strafakten), mit denen er seine Darstellung stützen will. Soweit er diesbezüglich überhaupt eine rechtsgenügend begründete Sachverhaltsrüge erhebt und nicht bloss seine eigene Sichtweise wiederholt und insbesondere pauschal auf die Strafakten oder Teile davon verweist, folgt aus seinen Ausführungen jedoch nicht, dass das Obergericht die Glaubhaftigkeit der Einwendungen willkürlich verneint hätte. Das Obergericht hat anerkannt, dass diese Urkunden Indizien für die Darstellung des Beschwerdeführers darstellen können, hat diese aber als zu wenig gewichtig erachtet. Es ist weder genügend dargetan noch ersichtlich, weshalb es damit ihre Bedeutung offensichtlich verkannt oder unhaltbare Schlussfolgerungen daraus gezogen haben sollte.
2.3.4. Der Beschwerdeführer macht sodann geltend, die Vorinstanz hätte zusätzliche Abklärungen zu den Umständen der Zession treffen müssen, dies umso mehr, als er die Einvernahme von F._ als Zeugin angeboten hätte.
Abgesehen von der offerierten Zeugeneinvernahme legt er nicht dar, welche Abklärungen das Obergericht hätte vornehmen sollen. Er geht auch nicht auf die Gründe ein, weshalb sich bereits das Obergericht nicht mehr mit der Frage beschäftigte, ob die Einvernahme von F._ als Zeugin geboten gewesen wäre oder nicht.
2.3.5. Schliesslich macht der Beschwerdeführer geltend, das Obergericht hätte im Rahmen des Untersuchungsgrundsatzes der richterlichen Fragepflicht nach <ref-law> nachkommen müssen, falls seine Ausführungen tatsächlich nicht schlüssig gewesen sein sollten.
Der Zweck der Fragepflicht nach <ref-law> besteht darin, dass eine Partei nicht wegen Unbeholfenheit ihres Rechts verlustig gehen soll, indem der Richter bei klaren Mängeln der Parteivorbringen helfend eingreifen soll. Sie dient jedoch nicht dazu, die Mitwirkung der Parteien bei der Sachverhaltsfeststellung zu ersetzen oder prozessuale Nachlässigkeiten einer Partei auszugleichen. Sie trägt dem Gericht auch nicht auf, einer Partei bei der Beweisführung behilflich zu sein (Urteil 5A_921/2014 vom 11. März 2015 E. 3.4.2 mit Hinweisen). Es bestand deshalb für das Obergericht kein Anlass, dem anwaltlich vertretenen Beschwerdeführer unter die Arme zu greifen. Der Beschwerdeführer bestreitet zudem nicht, dass die Parteien selbst bei Geltung des Untersuchungsgrundsatzes an der Sachverhaltsermittlung mitzuwirken haben.
2.3.6. Die Beschwerde erweist sich damit als unbegründet, soweit auf sie einzutreten ist.
3.
Bei diesem Ausgang des Verfahrens trägt der Beschwerdeführer die Gerichtskosten (<ref-law>). Der Beschwerdegegnerin sind keine zu ersetzenden Aufwendungen entstanden.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 15'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 23. August 2016
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Escher
Der Gerichtsschreiber: Zingg