Sachverhalt:
A.
A.a. A._, U._, (Gesuchsgegner, Beschwerdeführer) bewarb sich im Dezember 2015 erfolgreich um eine Stelle bei der B._ AG, U._, (Gesuchstellerin, Beschwerdegegnerin) in V._. Noch vor seinem Stellenantritt annullierte die Gesuchstellerin diese Anstellung aufgrund von Einträgen über den Gesuchsgegner im sog. Global Tracking System (nachfolgend: GTS). Beim GTS handelt es sich um eine von der Gesuchstellerin geführte Datenbank, in der sicherheitsrelevante Informationen über Personen registriert werden.
A.b. Mit Urteil vom 6. Februar 2018 verpflichtete das Arbeitsgericht Zürich die Gesuchstellerin unter Strafandrohung im Sinne von <ref-law>, dem Gesuchsgegner Auskunft über dessen Eintrag im GTS zu geben und ihm namentlich Inhalt, Zweck, Herkunft und Verwendung dessen Eintrags schriftlich und unter Beilage des Eintrages mitzuteilen (Dispositiv-Ziffer 1; nachfolgend: Erkenntnisentscheid).
Gegen diesen Entscheid erhob die Gesuchstellerin Berufung an das Obergericht des Kantons Zürich. Alsdann reichte sie im laufenden Berufungsverfahren einen teilweise - d.h. in Bezug auf die Namen der im System als Ersteller der fraglichen Einträge erfassten Personen - geschwärzten GTS-Auszug betreffend den Gesuchsgegner ins Recht und ersuchte um Abschreibung des Verfahrens zufolge Gegenstandslosigkeit.
Mit Urteil vom 19. Dezember 2018 wies das Obergericht des Kantons Zürich die Berufung der Gesuchstellerin ab und bestätigte den erstinstanzlichen Erkenntnisentscheid. Hinsichtlich der beantragten Abschreibung des Verfahrens wurde erwogen, eine solche komme nicht in Frage, zumal die Gesuchstellerin ihrer Herausgabepflicht mit den eingereichten Auszügen, die keine konkreten Rückschlüsse auf angebliche Vorkommnisse und die Herkunft der Daten zuliessen, nicht vollständig nachgekommen sei.
A.c. Nachdem der Gesuchsgegner die Gesuchstellerin am 8. bzw. 16. April 2019 aufgefordert hatte, ihm bis am 22. resp. 23. April 2019 umfassend Auskunft zu gewähren, kontaktierte die Gesuchstellerin die durch die Herausgabepflicht tangierten Drittpersonen. Zwei dieser betroffenen Personen erklärten sich nicht damit einverstanden, dass ihre Namen gegenüber dem Gesuchsgegner offengelegt würden.
Auf die entsprechenden Begehren dieser Drittpersonen hin erliess das Einzelgericht Audienz am Bezirksgericht Zürich am 18. April 2019 einen superprovisorischen Massnahmeentscheid, mit dem der Gesuchstellerin mit sofortiger Wirkung untersagt wurde, dem Gesuchsgegner oder anderen Dritten Auszüge oder Informationen aus oder im Zusammenhang mit dem GTS zu überlassen, aus denen sich die Namen oder andere Personendaten der beiden Drittpersonen ergeben oder ableiten lassen (nachfolgend: Massnahmeentscheid).
B.
B.a. Mit Eingabe vom 23. April 2019 machte die Gesuchstellerin beim Einzelgericht Audienz am Bezirksgericht Zürich ein Verfahren betreffend Einstellung der Vollstreckung anhängig, in dem sie folgende Anträge stellte und deren superprovisorische Anordnung verlangte:
"Die Vollstreckung von Dispositiv-Ziffer 1 des Urteils des Arbeitsgerichts Zürich vom 6. Februar 2018 (Geschäft Nr. xxx), einschliesslich Vollstreckungsmassnahmen (Überweisung an den Strafrichter zur Bestrafung der Organe der Gesuchstellerin nach <ref-law>), sei für die Dauer der Aufrechterhaltung des mit Urteil vom 18. April 2019 durch das Einzelgericht Audienz angeordneten Verbots (Geschäft Nr. yyy) einzustellen, soweit das genannte Urteil die Gesuchstellerin verpflichtet, dem Gesuchsgegner Auszüge oder Informationen aus oder im Zusammenhang mit dem Global Tracking System der Gesuchstellerin an den Gesuchsgegner herauszugeben oder auf andere Weise bekanntzugeben oder zugänglich zu machen, aus denen sich die Namen und andere Personendaten der Gesuchsteller im Geschäft Nr. yyy des Einzelgerichts Audienz ergeben oder ableiten lassen."
Das Einzelgericht Audienz gab dem Antrag auf superprovisorische Einstellung der Vollstreckung nicht statt.
Mit Urteil vom 8. Mai 2019 entschied das Einzelgericht Audienz wie folgt:
"1. Die Vollstreckung des Urteils des Arbeitsgerichts Zürich vom 6. Februar 2018 (Geschäfts-Nr. xxx) wird bis zum rechtskräftigen Entscheid des Prosequierungsgerichts im Umfang des mit Urteil vom 18. April 2019 durch das Einzelgericht Audienz angeordneten Verbots (Geschäfts-Nr. yyy) eingestellt und die in Dispositivziffer 1 des erstgenannten Urteils angedrohte Bestrafung nach <ref-law> für dieselbe Dauer aufgehoben.
2. Wird das im Verfahren yyy superprovisorisch angeordnete Verbot vor Abschluss des Prosequierungsverfahrens aufgehoben oder verstreicht die Prosequierungsfrist im genannten Verfahren ungenutzt, fällt die Einstellung der Vollstreckung mit der Vollstreckbarkeit dahin und die angedrohte Bestrafung nach <ref-law> lebt wieder auf.
3. Der Gesuchstellerin wird verboten, während der Dauer der Einstellung der Vollstreckung Einträge in ihrem Global Tracking System, die am 6. Februar 2018 bestanden haben und den Gesuchsgegner betreffen, abzuändern oder zu löschen.
Im Widerhandlungsfall werden die Organe der Gesuchstellerin wegen Ungehorsams gegen eine amtliche Verfügung im Sinne von <ref-law> mit Busse bis Fr. 10'000.-- bestraft.
4. Die Gesuchstellerin wird verpflichtet, dem Gesuchsgegner alle drei Monate, erstmals per 1. Oktober 2019, über den Stand des Verfahrens yyy und des darauf folgenden Prosequierungsverfahrens in geeigneter Form zu berichten.
5. Die Entscheidgebühr von Fr. 4'000.-- wird der Gesuchstellerin im Umfang von Fr. 1'000.-- und dem Gesuchsgegner im Umfang von Fr. 3'000.-- auferlegt. Sie wird im Gesamtumfang von der Gesuchstellerin bezogen, ist ihr aber vom Gesuchsgegner anteilsmässig zu ersetzen.
6. Der Gesuchsgegner wird verpflichtet, der Gesuchstellerin eine reduzierte Parteientschädigung von Fr. 4'847.-- zu bezahlen."
B.b. Mit Urteil vom 12. Dezember 2019 hob das Obergericht des Kantons Zürich in teilweiser Gutheissung der vom Gesuchsgegner erhobenen Beschwerde Dispositiv-Ziffer 5 des Urteils des Einzelgerichts Audienz am Bezirksgericht Zürich vom 8. Mai 2019 auf und ersetzte es durch die folgende Fassung: "5. Es werden keine Kosten erhoben" (Dispositiv-Ziffer 1). Im Übrigen wies es die Beschwerde ab (Dispositiv-Ziffer 2). Für das Beschwerdeverfahren erhob das Obergericht keine Kosten (Dispositiv-Ziffer 3), es verpflichtete den Gesuchsgegner hingegen zur Leistung einer Parteientschädigung von Fr. 4'300.-- an die Gesuchstellerin (Dispositiv-Ziffer 4).
C.
Mit Beschwerde in Zivilsachen beantragt der Gesuchsgegner dem Bundesgericht, es seien Dispositiv-Ziffern 2 und 4 des Urteils des Obergerichts des Kantons Zürich vom 12. Dezember 2019 aufzuheben und es sei in Dispositiv-Ziffer 1 des Urteils des Arbeitsgerichts Zürich vom 6. Februar 2018 (Geschäfts-Nr. xxx) die angedrohte Bestrafung nach <ref-law> wieder in Kraft zu setzen. Eventualiter seien Dispositiv-Ziffern 2 und 4 des angefochtenen Urteils aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Die Beschwerdegegnerin beantragt, es sei auf die Beschwerde nicht einzutreten, eventualiter sei diese abzuweisen. Die Vorinstanz hat auf eine Vernehmlassung verzichtet.
Der Beschwerdeführer hat dem Bundesgericht am 8. Juni 2020 eine Replik, die Beschwerdegegnerin hat ihm am 25. Juni 2020 eine Duplik eingereicht.

Erwägungen:
1.
Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-law>; <ref-ruling> E. 2.1).
1.1. Entscheide über vorsorgliche Massnahmen gelten nur als Endentscheide, wenn sie in einem eigenständigen Verfahren ergehen. Selbständig eröffnete Massnahmenentscheide, die vor oder während eines Hauptverfahrens erlassen werden und nur für die Dauer des Hauptverfahrens Bestand haben bzw. unter der Bedingung, dass ein Hauptverfahren eingeleitet wird, stellen Zwischenentscheide im Sinne von <ref-law> dar (<ref-ruling> E. 1.1.1; <ref-ruling> E. 1.2 S. 79; <ref-ruling> E. 1.1 S. 327 f.; je mit Verweisen; vgl. auch <ref-ruling> E. 1.1; vgl. etwa auch Urteil 4A_638/2018 vom 18. März 2019 E. 4 betr. die vorläufige Einstellung der Betreibung nach <ref-law>).
Wie im angefochtenen Entscheid ausdrücklich festgehalten, war Gegenstand des vorinstanzlichen Verfahrens "bloss eine vorläufige - und nicht eine definitive - Einstellung der Vollstreckung". Wie auch in der Beschwerdeschrift zutreffend hervorgehoben wird, betrifft "[d]as angefochtene Urteil [...] die einstweilige Einstellung der Realvollstreckung des Auskunftsrechts [Hervorhebung hinzugefügt]". Die angeordnete Einstellung der Vollstreckung ist damit lediglich provisorischer Natur, indem sie nur Bestand hat, bis ein rechtskräftiger Entscheid des Prosequierungsgerichts vorliegt oder bis der ergangene Massnahmeentscheid infolge Aufhebung oder unbenutzten Ablaufs der Prosequierungsfrist dahinfällt. Erst nach Abschluss des Prosequierungsverfahrens wird das Vollstreckungsgericht endgültig über die Einstellung der Vollstreckung befinden. Es handelt sich beim angefochtenen Entscheid demnach um einen Zwischenentscheid im Sinne von <ref-law>.
Der anwaltlich vertretene Beschwerdeführer bringt zwar in seiner Beschwerdeschrift unzutreffenderweise vor, die Beschwerde richte sich gegen einen Endentscheid gemäss <ref-law>. Er beruft sich jedoch zu Recht nicht etwa darauf, er habe sich auf die Rechtsmittelbelehrung im angefochtenen Entscheid verlassen dürfen, wonach ein Endentscheid im Sinne dieser Bestimmung vorliege. Einer Partei darf wegen einer unrichtigen Rechtsmittelbelehrung zwar kein Nachteil erwachsen (<ref-law>), jedoch vermag eine falsche Rechtsmittelbelehrung nicht eine im Gesetz nicht vorgesehene Rechtsmittelmöglichkeit zu begründen (<ref-ruling> E. 1.2 S. 473).
1.2. Gegen selbständig eröffnete Zwischenentscheide, die weder die Zuständigkeit noch den Ausstand betreffen (vgl. <ref-law>), ist die Beschwerde nur zulässig, wenn sie einen nicht wieder gutzumachenden Nachteil bewirken können (<ref-law>) 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 (<ref-law>). Der nicht wieder gutzumachende Nachteil im Sinne von <ref-law> muss ein Nachteil rechtlicher Natur sein, der auch durch einen für die beschwerdeführende Partei günstigen Entscheid in der Zukunft nicht mehr behoben werden kann (<ref-ruling> E. 1.2 S. 479; <ref-ruling> E. 1.3; <ref-ruling> E. 1.2; je mit Hinweisen). Rein tatsächliche Nachteile wie die Verlängerung oder Verteuerung des Verfahrens reichen nicht aus (<ref-ruling> E. 1.2 S. 479; <ref-ruling> E. 2.2 S. 801; <ref-ruling> E. 1.2; je mit Hinweisen). Die selbständige Anfechtbarkeit von Zwischenentscheiden bildet aus prozessökonomischen Gründen eine Ausnahme vom Grundsatz, dass sich das Bundesgericht mit jeder Angelegenheit nur einmal befassen soll (<ref-ruling> E. 1.2 S. 479; <ref-ruling> E. 2.2 S. 801; <ref-ruling> E. 1.2 S. 81). Die Ausnahme ist restriktiv zu handhaben (<ref-ruling> E. 2.1 S. 479; <ref-ruling> E. 2.2 S. 95).
Während die frühere Rechtsprechung bei Zwischenentscheiden, mit denen vorsorgliche Massnahmen erlassen oder verweigert wurden, einen nicht wieder gutzumachenden Nachteil regelmässig bejahte (<ref-ruling> E. 3.1 S. 87 mit Hinweisen auf die frühere Rechtsprechung), wird nach der neueren, nunmehr gefestigten Rechtsprechung verlangt, dass in der Beschwerdebegründung aufgezeigt wird, inwiefern im konkreten Fall ein nicht wieder gutzumachender Nachteil rechtlicher Natur drohe (<ref-ruling> E. 1.2 S. 479 f.; <ref-ruling> E. 1.1 S. 328 f.).
1.3. Im zu beurteilenden Fall ist nicht ersichtlich, dass diese Voraussetzungen erfüllt wären. Selbst wenn der Beschwerdeführer mit seinem Vorbringen in der Replik zu hören wäre, die Beschwerde sei "allein schon aufgrund von Art. 93 Abs. 1 lit. d [gemeint: lit. b] BGG ohne weiteres zulässig, da bei Gutheissung der vorliegenden Beschwerde sofort ein Endentscheid herbeigeführt und so ein bedeutender Aufwand an Zeit bzw. Kosten für ein weitläufiges Beweisverfahren erspart würde", könnte ihm nicht gefolgt werden. Es geht weder aus seinen Ausführungen hervor noch ist ersichtlich, um welches konkrete Beweisverfahren es sich dabei handeln, geschweige denn, inwiefern dieses besonders weitläufig im Sinne von <ref-law> sein soll.
Ebenso wenig lässt sich ein nicht wieder gutzumachender Nachteil rechtlicher Natur (<ref-law>) daraus ableiten, dass der angefochtene Entscheid mit einer Verzögerung der vom Beschwerdeführer angestrebten sofortigen Vollstreckung des Erkenntnisentscheids verbunden ist, zumal es sich bei der Verlängerung des Verfahrens nach der Rechtsprechung um einen rein tatsächlichen Nachteil handelt, der keine sofortige Anfechtung rechtfertigt (<ref-ruling> E. 1.2 S. 479; <ref-ruling> E. 2.2 S. 801; <ref-ruling> E. 1.2; je mit Hinweisen). Ausserdem verkennt der Beschwerdeführer mit seinen Ausführungen zum rechtlichen Gehör (<ref-law>), dass er im Rahmen des definitiven Entscheids über die Einstellung der Vollstreckung nochmals anzuhören sein wird.
Die Voraussetzungen für eine ausnahmsweise Anfechtbarkeit eines Zwischenentscheids nach <ref-law> sind demnach nicht erfüllt. Auf die Beschwerde ist nicht einzutreten.
2.
Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Auf die Beschwerde wird nicht eingetreten.
2.
Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
3.
Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 16. Juli 2020
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Leemann