Sachverhalt:
A.
A.a. Die A._ Ltd (Beklagte 1, Beschwerdeführerin 1), eine nach den Gesetzen der U._ errichtete Gesellschaft und die chinesische B._ Corp. (Beklagte 2, Beschwerdeführerin 2) sind Konzerntöchter der D._ Corporation.
Die C._ Limited ist eine nach den Gesetzen der U._ errichtete Gesellschaft (Klägerin, Beschwerdegegnerin). Sie verpflichtete sich mit dem schweizerischen Recht unterstehenden Cooperation Agreement vom 30. Juli 2012, die D._ Corporation bei der Ausweitung ihres petrochemischen Geschäfts auf den V._ Markt insoweit zu unterstützen, als sie insbesondere vermittelnd tätig werden sollte mit dem Ziel, in verschiedenen Streitpunkten mit V._ staatlicher Erdölgesellschaft E._ eine Einigung zu finden.
Nach erzielter Einigung mit E._ forderte die C._ Limited auf der Grundlage des Cooperation Agreements einen Prozentsatz der Vergleichssumme als Honorar. Die A._ Ltd und die B._ Corp. widersetzten sich. Sie machten im Wesentlichen geltend, die C._ Limited habe sich nicht bzw. zumindest nicht hinreichend bemüht, einen Vergleich zu erzielen, sondern sei eher kontraproduktiv tätig geworden, weshalb ihr kein Honorar zustehe.
B.
B.a. Am 3. November 2016 leitete die C._ Limited gegen die A._ Ltd und die B._ Corp. ein Schiedsverfahren nach den Swiss Rules of International Arbitration (2012) der Swiss Chambers' Arbitration Institution ein und forderte ein Honorar von über 95 Millionen USD, wobei sie die Forderung im Laufe des Verfahrens auf knapp 89 Millionen USD reduzierte.
Die Beklagten beantragten die Abweisung der Schiedsklage.
Vom 11. bis 13. Juni 2018 fand die mündliche Verhandlung in Genf statt, an der auch diverse Zeugen befragt wurden.
B.b. Mit Schiedsspruch vom 7. Januar 2019 hiess das aus drei Mitgliedern bestehende Schiedsgericht mit Sitz in Genf die Schiedsklage teilweise gut und verpflichtete die Beklagten im Wesentlichen zur Zahlung von knapp USD 40 Millionen an die Klägerin.
Das Schiedsgericht qualifizierte den für die vorliegende Streitigkeit relevanten Teil des Cooperation Agreements als Mäklervertrag im Sinne von <ref-law> und schloss, der Vergleich mit E._ sei durch Bemühungen (" through efforts ") der Klägerin geschlossen worden, weshalb ihr als Mäklerhonorar der vertraglich vereinbarte Anteil an der Vergleichssumme zustehe.
C.
Mit Beschwerde in Zivilsachen begehren die Beklagten, es sei der Schiedsspruch vom 2. August 2016 des Schiedsgerichts mit Sitz in Genf unter entsprechenden Kosten- und Entschädigungsfolgen aufzuheben.
Die Beschwerdegegnerin beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das Schiedsgericht hat auf Vernehmlassung verzichtet.
Die Parteien haben dem Bundesgericht eine Replik respektive eine Duplik eingereicht.
D.
Mit Präsidialverfügung vom 14. März 2019 wurde der Beschwerde antragsgemäss die aufschiebende Wirkung erteilt.

Erwägungen:
1.
Nach <ref-law> ergeht der Entscheid des Bundesgerichts in einer Amtssprache, in der Regel in jener des angefochtenen Entscheids. Der angefochtene Entscheid ist in englischer Sprache abgefasst. Da es sich dabei nicht um eine Amtssprache handelt und die Parteien ihre dem Bundesgericht eingereichten Rechtsschriften in Übereinstimmung mit <ref-law> i.V.m. <ref-law> auf Deutsch (Beschwerdeführerinnen) und auf Französisch (Beschwerdegegnerin) verfassten, ergeht der Entscheid des Bundesgerichts praxisgemäss in der Sprache der Beschwerde (<ref-ruling> E. 1).
2.
Im Bereich der internationalen Schiedsgerichtsbarkeit ist die Beschwerde in Zivilsachen unter den Voraussetzungen der Art. 190-192 IPRG (SR 291) zulässig (<ref-law>).
2.1. Der Sitz des Schiedsgerichts befindet sich vorliegend in Genf. Alle Parteien hatten im massgebenden Zeitpunkt ihren Sitz ausserhalb der Schweiz (<ref-law>). Da die Parteien die Geltung des 12. Kapitels des IPRG nicht ausdrücklich ausgeschlossen haben, gelangen die Bestimmungen dieses Kapitels zur Anwendung (<ref-law>).
2.2. Die Beschwerdeführerinnen sind vor dem Schiedsgericht teilweise unterlegen, womit sie vom angefochtenen Entscheid besonders berührt sind und ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung haben (<ref-law>). Die Beschwerde ist innert Frist eingereicht worden (<ref-law>), womit vorbehältlich rechtsgenüglicher Rügen auf die Beschwerde einzutreten ist.
2.3. Zulässig sind allein die Rügen, die in <ref-law> abschliessend aufgezählt sind (<ref-ruling> E. 5 S. 187; <ref-ruling> E. 1a S. 53; <ref-ruling> E. 1a S. 282). Nach <ref-law> prüft das Bundesgericht nur die Rügen, die in der Beschwerde vorgebracht und begründet worden sind; dies entspricht der in <ref-law> für die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht vorgesehenen Rügepflicht (<ref-ruling> E. 5 S. 187 mit Hinweis). Appellatorische Kritik ist unzulässig (<ref-ruling> E. 3.1 S. 567; <ref-ruling> E. 3b S. 382).
2.4. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den das Schiedsgericht festgestellt hat (<ref-law>). Dazu gehören sowohl die Feststellungen über den Lebenssachverhalt, der dem Streitgegenstand zugrunde liegt, als auch jene über den Ablauf des schiedsgerichtlichen Verfahrens, also die Feststellungen über den Prozesssachverhalt, zu dem namentlich die Anträge der Parteien, ihre Tatsachenbehauptungen, rechtlichen Erörterungen, Prozesserklärungen und Beweisvorbringen, der Inhalt einer Zeugenaussage, einer Expertise oder die Feststellungen anlässlich eines Augenscheins gehören (<ref-ruling> E. 1.3.1 mit Hinweisen). Das Bundesgericht kann die Sachverhaltsfeststellung des Schiedsgerichts weder berichtigen noch ergänzen, selbst wenn diese offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> sowie <ref-law> ausschliesst). Allerdings kann das Bundesgericht die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids überprüfen, wenn gegenüber diesen Sachverhaltsfeststellungen zulässige Rügen im Sinne von <ref-law> vorgebracht oder ausnahmsweise Noven berücksichtigt werden (<ref-ruling> E. 2.2.1 S. 34; <ref-ruling> E. 3.1 S. 567; <ref-ruling> E. 5 S. 141; je mit Hinweisen). Wer sich auf eine Ausnahme von der Bindung des Bundesgerichts an die tatsächlichen Feststellungen des Schiedsgerichts beruft und den Sachverhalt gestützt darauf berichtigt oder ergänzt wissen will, hat mit präzisen Aktenhinweisen darzulegen, dass entsprechende Sachbehauptungen bereits im schiedsgerichtlichen Verfahren prozesskonform aufgestellt worden sind (vgl. <ref-ruling> E. 2a S. 486; <ref-ruling> E. 1c S. 473; je mit Hinweisen; vgl. auch <ref-ruling> E. 2 S. 90).
3.
Die Beschwerdeführerinnen werfen dem Schiedsgericht in verschiedener Hinsicht eine Verletzung des rechtlichen Gehörs sowie des Grundsatzes der Gleichbehandlung der Parteien vor (<ref-law>).
3.1.
<ref-law> lässt die Anfechtung allein wegen der zwingenden Verfahrensregeln gemäss <ref-law> zu. Danach muss das Schiedsgericht insbesondere den Anspruch der Parteien auf rechtliches Gehör wahren. Dieser entspricht - mit Ausnahme des Anspruchs auf Begründung - grundsätzlich dem in <ref-law> gewährleisteten Verfassungsrecht. Die Rechtsprechung leitet daraus insbesondere das Recht der Parteien ab, sich über alle für das Urteil wesentlichen Tatsachen zu äussern, ihren Rechtsstandpunkt zu vertreten, ihre entscheidwesentlichen Sachvorbringen mit tauglichen sowie rechtzeitig und formrichtig offerierten Mitteln zu beweisen, sich an den Verhandlungen zu beteiligen und in die Akten Einsicht zu nehmen (<ref-ruling> E. 4.1.1; <ref-ruling> E. 5 S. 38; <ref-ruling> E. 2c; je mit Hinweisen). Der Anspruch auf rechtliches Gehör in einem kontradiktorischen Verfahren nach Art. 182 Abs. 3 und <ref-law> umfasst nach ständiger Rechtsprechung nicht auch den Anspruch auf Begründung eines internationalen Schiedsentscheids (<ref-ruling> E. 6.1 mit Hinweisen). Dennoch ergibt sich daraus eine minimale Pflicht der Schiedsrichter, die entscheiderheblichen Fragen zu prüfen und zu behandeln. Diese Pflicht verletzt das Schiedsgericht, wenn es aufgrund eines Versehens oder eines Missverständnisses rechtserhebliche Behauptungen, Argumente, Beweise oder Beweisanträge einer Partei unberücksichtigt lässt (<ref-ruling> E. 4.1.1; <ref-ruling> E. 5.2 mit Hinweisen).
Der Anspruch auf Gleichbehandlung gebietet, dass das Schiedsgericht die Parteien in allen Verfahrensabschnitten (einschliesslich einer allfälligen Verhandlung, unter Ausschluss der Urteilsberatung; vgl. Urteil 4A_360/2011 vom 31. Januar 2012 E. 4.1) gleich behandelt (BGE <ref-ruling> E. 6.1 S. 143) und nicht der einen Partei gewährt, was der anderen verwehrt wird (Urteile 4A_80/2017 vom 25. Juli 2017 E. 3.1.2; 4A_636/2014 vom 16. März 2015 E. 4.2). Beiden Parteien muss die gleiche Möglichkeit eingeräumt werden, im Prozess ihren Standpunkt zu vertreten (<ref-ruling> E. 4.1.1 S. 361).
3.2.
3.2.1. Die Beschwerdeführerinnen erblicken eine Verletzung ihres Anspruchs auf rechtliches Gehör in erster Linie darin, dass das Schiedsgericht den Brief von F._, der einst Chief Executive Officer (CEO) von E._ war, als gewöhnlichen Urkundenbeweis abnahm, anstatt eine schriftliche Zeugenaussage (" witness statement ") einzufordern und ihn im Anschluss hiernach als Zeugen anzuhören. Mangels Zeugeneinvernahme sei es ihnen verwehrt gewesen, F._ im Rahmen eines Kreuzverhörs (" cross-examination ") zu befragen. Die Beschwerdeführerinnen bezeichnen die im Brief enthaltenen Informationen als offensichtlich falsch sowie irreführend und bemängeln, dass das Schiedsgericht in seinem Schiedsurteil zentral auf diesen Brief abgestellt habe.
3.2.2. Wie die Beschwerdegegnerin in ihrer Antwort zutreffend vorbringt, beanstanden die Beschwerdeführerinnen im Ergebnis, dass das Schiedsgericht F._ nicht als Zeugen einvernahm. Es ist allerdings weder ersichtlich noch dargetan, warum es hierzu verpflichtet gewesen sein sollte. Die Beschwerdeführerinnen zeigen denn auch nicht auf, inwiefern das Schiedsgericht ein zwingendes Verfahrensrecht im Sinne von <ref-law> und <ref-law> verletzt haben könnte (vgl. vorstehend E. 3.1). Wenn die Beschwerdeführerinnen in ihrer Replik vor Bundesgericht sodann einwenden, die Beschwerdegegnerin trage die Beweislast für ihr vertragskonformes Tätigwerden als Mäklerin, mag das zutreffen. Der Einwand geht jedoch an der Problematik vorbei und es ergeht daraus, dass die Beschwerdeführerinnen sich richtig besehen vielmehr gegen die Beweiswürdigung respektive das daraus resultierende Beweisergebnis wenden. Auch indem sie ferner beanstanden, dass das Schiedsgericht den von F._ verfassten Brief als Urkundenbeweis entgegennahm, anstatt ihn ohne Weiteres aus dem Recht zu weisen, richten sie sich gegen die Würdigung der Beweise des Schiedsgerichts. Hiermit übergehen sie, dass das Bundesgericht die Sachverhaltsfeststellung des Schiedsgerichts weder berichtigen noch ergänzen kann, selbst wenn diese offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (vgl. hierzu vorstehend E. 2.4).
Wie dem von den Beschwerdeführerinnen selbst zitierten Auszug aus dem Schiedsspruch zu entnehmen ist, ging das Schiedsgericht auf die vorgebrachten Argumente der Beschwerdeführerinnen ein und gewährte ihnen insofern das rechtliche Gehör. Es führte namentlich aus, die Behauptung, F._ sei für die Erstellung des Briefes durch die Beschwerdegegnerin entlöhnt worden, sei unsubstanziiert und es sei sich bewusst, " that the Respondents [Beschwerdeführerinnen] did not have an opportunity to cross-examine Mr. F._, it [the Arbitral Tribunal] also notes that it has not been presented with any significant reasons to conclude that the overall message of the letter is manifestly false or misleading. On this basis, the Tribunal sees no need to reject the letter outright, but will refer to it where necessary, taking these circumstances into account. " Insofern vor diesem Hintergrund auf die Rüge überhaupt einzutreten wäre, ist sie unbegründet.
3.3. Die Beschwerdeführerinnen rügen sodann, das Schiedsgericht habe sowohl ihren Gehörsanspruch als auch den Grundsatz der Gleichbehandlung der Parteien (<ref-law>) verletzt, indem es G._ zur mündlichen Zeugenanhörung vorlud. Zur Begründung führen die Beschwerdeführerinnen im Wesentlichen an, der von der Beschwerdegegnerin angerufene G._ sei im Gegensatz zu F._ als Zeuge einvernommen worden, obwohl er vorgängig keine schriftliche Zeugenaussage einreichte.
Ziffer 35 der Procedural Order No. 1 lautet - wie die Beschwerdeführerinnen selbst zitieren - wie folgt: "[T] he Arbitral Tribunal may order a witness to give testimony at the hearing if such testimony is relevant to the case and material to its outcome ". Wenn die Beschwerdeführerinnen ausführen, es hätte keinen Grund gegeben, die Ausnahmeregelung gemäss Ziffer 35 Procedural Order No. 1 anzuwenden, gestehen sie implizit ein, dass das Schiedsgericht grundsätzlich befugt war, Zeugen vorzuladen, ohne entsprechenden Parteiantrag und ohne dass diese vorher schriftlich hätten aussagen müssen. Ihre Kritik bezieht sich im Ergebnis einzig auf die Anwendung der Ausnahmeregelung selbst. Wenn sie ferner beanstanden, das Schiedsgericht habe die Zeitspanne von 24 Tagen zu Unrecht als zu kurz erachtet, um eine schriftliche Zeugenaussage zu berücksichtigen, verkennen sie, dass sie auch insoweit die Anwendung der Verfahrensordnung des Schiedsgerichts kritisieren, welche das Bundesgericht angesichts seiner beschränkten Kognition in der internationalen Schiedsgerichtsbarkeit nicht überprüfen kann (vgl. vorstehend E. 2.3). Inwiefern es einer Ungleichbehandlung der Parteien respektive einer Bevorzugung der Beschwerdegegnerin unter Verletzung von <ref-law> gleichkam, wenn das Schiedsgericht G._ ohne entsprechenden Parteiantrag als Zeugen einvernahm, die gleiche Ausnahmeregelung aber nicht betreffend F._ anwandte, ist der Beschwerde nicht zu entnehmen.
Dem Vorwurf der Beschwerdeführerinnen, sie hätten sich mangels vorgängig eingeholter schriftlicher Aussage nicht hinreichend auf das Kreuzverhör G._ vorbereiten können, ist entgegenzuhalten, dass sie selbst nicht behaupten, an diesem dem Schiedsgericht mitgeteilten Einwand festgehalten respektive ihre Kritik anlässlich der mündlichen Verhandlung vom 11. bis 13. Juni 2018 erneuert zu haben. Mithin lassen sie auch in ihrer Replik das Vorbringen der Beschwerdegegnerin in der Beschwerdeantwort unbeanstandet, sie hätten im Rahmen der mündlichen Verhandlung einzig eine kurze Pause nach der Befragung durch das Schiedsgericht verlangt, um sich auf das Kreuzverhör vorbereiten zu können. Zumindest angesichts der im Anschluss an die Befragung durch das Schiedsgericht antragsgemäss gewährten Pause zur Vorbereitung des Kreuzverhörs kann keine Rede von einer Gehörsverletzung sein. Da sich auch die Beschwerdegegnerin mit der besagten Pause begnügen musste, um sich ihrerseits auf das Kreuzverhör vorzubereiten, wurde den Parteien auch insoweit die gleiche Möglichkeit eingeräumt, im Prozess ihren Standpunkt zu vertreten.
3.4. Die Beschwerdeführerinnen machen weiter geltend, es sei eine deutliche Präferenz des Schiedsgerichts für die Aussagen der von der Beschwerdegegnerin angerufenen Zeugen zu erkennen. Die jeweiligen Aussagen seien derweil gar höher gewertet worden als der Dokumentenbeweis, was weder zu rechtfertigen noch zu erklären sei und eine Verletzung des Prinzips der Gleichbehandlung der Parteien (<ref-law>) bedeute.
Die Beschwerdeführerinnen richten sich mit ihrer Kritik richtig besehen erneut gegen die Würdigung der Beweise des Schiedsgerichts respektive versuchen unter dem Deckmantel ihrer Rüge betreffend Ungleichbehandlung der Parteien eine Überprüfung des Beweisergebnisses des angefochtenen Schiedsspruchs herbeizuführen. Eine derartige Überprüfung des angefochtenen Entscheids ist indessen nicht die Aufgabe des Bundesgerichts, wenn es wie vorliegend mit Beschwerde in Zivilsachen bezüglich eines Entscheids der internationalen Schiedsgerichtsbarkeit angerufen wird (vgl. dazu vorstehend E. 2.3-2.4 sowie inbesondere <ref-ruling> E. 4.1.2 und Urteil 4A_220/2017 vom 8. Januar 2018 E. 3.1-3.2). Inwiefern das Schiedsgericht nicht beiden Parteien die gleiche Möglichkeit eingeräumt hätte, im Prozess ihren Standpunkt zu vertreten, ist nicht ersichtlich. Die Beschwerdeführerinnen beschränken sich vielmehr darauf, längere Ausführungen in Bezug auf die Würdigung des Schiedsgerichts einzelner Beweismittel zu machen. Hiermit vermögen sie nicht einmal - vom Bundesgericht in der internationalen Schiedsgerichtsbarkeit ohnehin ebenfalls nicht zu überprüfende (vgl. vorstehend E. 2.3-2.4) - Willkür bei der Würdigung der Beweise aufzuzeigen. Lediglich der guten Ordnung halber sei schliesslich erwähnt, dass entgegen dem, was der appellatorischen Rüge der Beschwerdeführerinnen entnommen werden könnte, das Schiedsgericht an keine starre Hierarchie der Beweismittel gebunden war, sondern diese frei zu würdigen hatte (vgl. Art. 24 Ziff. 2 der Swiss Rules: "The arbitral tribunal shall determine the admissibility, relevance, materiality, and weight of the evidence").
3.5. Auch insoweit die Beschwerdeführerinnen eine weitere Verletzung des rechtlichen Gehörs darin erblicken, dass das Schiedsgericht in Bezug auf die Quantifizierung des Mäklerhonorars den Vertragstext missachtet und gegen die Auslegungsregel "in dubio contra stipulatorem" verstossen habe, versuchen sie - wie bereits aus der Formulierung ihrer Rügen und erst recht aus der dazugehörigen Begründung ergeht - eine Überprüfung der Rechtsanwendung des Schiedsgerichts durch das Bundesgericht zu erreichen. Hiermit verkennen sie abermals die Kognition des Bundesgerichts, die sich im internationalen Schiedsverfahren auf die in <ref-law> abschliessend aufgezählten Rügegründe beschränkt (vgl. vorstehend E. 2.3), weshalb sie mit ihrer Kritik nicht gehört werden können. Denn die Beschwerdeführerinnen zeigen nicht auf, inwiefern die im Rahmen der internationalen Schiedsgerichtsbarkeit aus dem Anspruch auf rechtliches Gehör erwachsende minimale Pflicht des Schiedsgerichts, die entscheiderheblichen Fragen zu prüfen und zu behandeln (vgl. vorstehend E. 3.1), verletzt sein könnte.
4.
Die Beschwerde ist abzuweisen, soweit auf sie eingetreten werden kann. Die Gerichtskosten sind dementsprechend den unterliegenden Beschwerdeführerinnen gemeinsam - zu gleichen Teilen und unter solidarischer Haftung - aufzuerlegen (Art. 66 Abs. 1 und 5 BGG). Sie haben die Beschwerdegegnerin, die sich vor Bundesgericht durch ihren Anwalt vernehmen liess, ausserdem für das bundesgerichtliche Verfahren - wiederum zu gleichen Teilen und unter solidarischer Haftung - zu entschädigen (Art. 68 Abs. 1, 2 und 4 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 100'000.-- werden den Beschwerdeführerinnen auferlegt.
3.
Die Beschwerdeführerinnen haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 120'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Schiedsgericht mit Sitz in Genf schriftlich mitgeteilt.
Lausanne, 31. Juli 2019
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Hug