Sachverhalt:
A.
A._ Ltd., Katar (nachfolgend: Agentin, Beschwerdeführerin) und B._ A.S., Türkei (nachfolgend: Auftraggeberin, Beschwerdegegnerin) schlossen am 21. April 2007 einen Agenturvertrag ("Agency Agreement"). Die Agentin verpflichtete sich darin, Aufträge der Baubehörden in Katar im Zusammenhang mit dem sogenannten "North Highway Project" für die Auftraggeberin zu verschaffen und sollte dafür eine Kommission von 2 % pro vermittelten Auftrag erhalten. Der Vertrag enthielt in Art. 16 folgende Schiedsklausel:
"16.1 Any question, dispute or difference between the PARTIES arising out of or in connection with this AGREEMENT shall be settled amicably between the PARTIES. In the event of the PARTIES failing to reach an amicable settlement, the matter shall be referred to arbitration.
16.2 All disputes arising in connection with the AGREEMENT shall be finally settled under the Rules of Conciliation and Arbitration of the International Chamber of Commerce, Paris, by one or more arbitrators appointed in accordance with the said Rules.
16.3 The award shall designate who shall be responsible for the expenses of arbitration.
16.4 Arbitration shall take place in Zurich, Switzerland."
Art. 16 bestimmt ausserdem:
"This AGREEMENT shall be governed and construed in accordance with the Laws of Switzerland (Canton Zurich) ".
Der Agenturvertrag war seitens der Auftraggeberin durch C._ unterzeichnet worden.
A.a. Nachdem zwischen den Parteien Unstimmigkeiten im Zusammenhang mit dem Agenturvertrag entstanden waren, leitete die Agentin ein Schiedsverfahren (ICC Verfahren xxx) ein. Noch bevor sich das Schiedsgericht konstituieren konnte, schlossen die Parteien am 24. Januar 2010 einen Vergleich ("Settlement Agreement"). Die Auftraggeberin verpflichtete sich darin zu einer Zahlung von USD 7'800'000.--, wogegen die Agentin das Gesuch um Einleitung eines Schiedsverfahrens zurückzog. Ausserdem vereinbarten die Parteien in Art. 7 und 9 des "Settlement Agreement":
"Art. (7)
a) It is agreed that the agreed amount represent[s] the first party's full entitlements under the Qatar North Highway Project Contract.
b) The first party [die Agentin] shall be paid a commission of 1.75 % of the total amount of the additional Project value in the event that the second party [die Auftraggeberin] obtains an award of a new motorway section additional to the existing Contract with the services of the first party".
"Art. (9)
The Parties acknowledge that the Agency Agreement shall remain valid and effective for all its articles and conditions to the extent that they do not contradict with the provisions of this Agreement.
The parties have further agreed to refer the dispute arising under this Agreement to Qatari Courts, whereas all disputes arising under the Agency Agreement to Arbitration as set out in Article (16) of the Agency Agreement".
Nach Abschluss des Vergleichs vom 24. Januar 2010 vermittelte die Agentin zwei weitere Bauverträge mit den katarischen Baubehörden; die Verträge yyy und zzz. In der Folge kam es erneut zu Streitigkeiten. Die Agentin beanspruchte eine Provision von 1,75 % der Auftragssumme für die Verträge yyy und zzz oder QAR 42'970'747.--. Die Auftraggeberin bestritt einen Anspruch auf Provision.
Im Jahr 2012 reichte die Agentin zwei Klagen vor katarischen Gerichten ein. Die Auftraggeberin reagierte ebenfalls mit einer Klage. Die drei Klagen wurden vereinigt. Mit Urteil vom 26. März 2013 wies das erstinstanzliche katarische Gericht alle Klagen ab. Am 31. März 2014 wies das Berufungsgericht die von beiden Parteien erhobenen Berufungen ab. Die Agentin erhob Beschwerde beim Kassationshof von Katar. Dieser bestätigte mit Entscheid vom 2. Dezember 2014 die Entscheide des erstinstanzlichen und des Berufungsgerichts.
B.
Am 1. Dezember 2016 leitete die Agentin gestützt auf die Schiedsklausel in Art. 16 des Agenturvertrags ein Schiedsverfahren gemäss der Schiedsordnung der Internationalen Handelskammer in Paris (ICC) ein. Die Bestellung des von den Parteien beantragten Dreier-Schiedsgerichts wurde mit Entscheid des ICC-Schiedsgerichtshofs vom 27. April 2017 abgeschlossen. Am 28. Juni 2017 teilte das Schiedsgericht das Verfahren auf und beschränkte dieses in einer ersten Phase auf Fragen der Zuständigkeit und Zulässigkeit.
Mit Entscheid vom 22. Mai 2018 verneinte das Schiedsgericht seine Zuständigkeit. Es stellte fest, die Schiedsvereinbarung in Art. 16.2 des Agenturvertrages sei nicht gültig, da C._ nicht ermächtigt gewesen sei, für die Auftraggeberin eine Schiedsvereinbarung abzuschliessen und diese auch nicht nachträglich genehmigt worden sei. Überdies falle die Streitigkeit nicht in den Anwendungsbereich der Schiedsvereinbarung gemäss Art. 16.2 des Agenturvertrages. Schliesslich äusserte es sich in einem dritten Punkt zur Frage, ob die Streitsache nicht bereits abschliessend durch staatliche katarische Gerichte beurteilt worden sei, womit einem Entscheid des Schiedsgerichts die Einrede der res iudicata entgegenstünde. Die Ausführungen zur res iudicata erfolgten nur im Rahmen eines obiter dictum (als Hinweis an die Parteien), da das Schiedsgericht zuvor seine Zuständigkeit gestützt auf die ersten beiden Punkte verneint hatte und daher festhielt, mangels Zuständigkeit könne es auch nicht über die Frage der res iudicata entscheiden.
C.
Mit Beschwerde in Zivilsachen beantragt die Agentin dem Bundesgericht, es sei der Entscheid des Schiedsgerichtshofs (recte: Schiedsgerichts) der Internationalen Handelskammer (ICC) vom 22. Mai 2018 kostenfällig aufzuheben und es sei die Zuständigkeit des Schiedsgerichts festzustellen sowie die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Die Beschwerdegegnerin beantragt, auf die Beschwerde sei nicht einzutreten, eventualiter sei sie abzuweisen; unter Kosten- und Entschädigungsfolge. Das Schiedsgericht hat sich nicht vernehmen lassen.

Erwägungen:
1.
Nach <ref-law> ergeht der Entscheid des Bundesgerichts in einer Amtssprache, in der Regel in jener des angefochtenen Entscheids. Wurde dieser in einer anderen Sprache redigiert, verwendet das Bundesgericht die von den Parteien gewählte Amtssprache. Der angefochtene Entscheid ist in englischer Sprache abgefasst. Da es sich dabei nicht um eine Amtssprache handelt und sich die Parteien vor Bundesgericht der deutschen Sprache bedienen, ergeht der Entscheid des Bundesgerichts auf deutsch.
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 Zürich. Die Parteien hatten im massgebenden Zeitpunkt ihren Wohnsitz bzw. ihren Sitz ausserhalb der Schweiz (<ref-law>). Da sie die Geltung des 12. Kapitels des IPRG nicht ausdrücklich ausgeschlossen haben, gelangen die Bestimmungen dieses Kapitels zur Anwendung (<ref-law>).
2.2. Beim angefochtenen Schiedsentscheid handelt es sich um einen Endentscheid, in dem das Schiedsgericht seine Zuständigkeit verneinte. Dieser kann nach <ref-law> mit Beschwerde angefochten werden.
Die Beschwerde im Sinne von <ref-law> ist grundsätzlich rein kassatorischer Natur, d.h. sie kann nur zur Aufhebung des angefochtenen Entscheids führen (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> ausschliesst, soweit dieser dem Bundesgericht erlaubt, in der Sache selbst zu entscheiden). Soweit der Streit die Zuständigkeit des Schiedsgerichts oder dessen Zusammensetzung betrifft, gilt davon eine dahingehende Ausnahme, dass das Bundesgericht selber die Zuständigkeit oder die Unzuständigkeit des Schiedsgerichts feststellen bzw. über die Ablehnung des betreffenden Schiedsrichters befinden kann (<ref-ruling> E. 3.3.4 S. 616 mit Hinweisen). Der Antrag der Beschwerdeführerin ist demnach zulässig.
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).
3.
Die Beschwerdegegnerin beantragt Nichteintreten auf die Beschwerde. Das Schiedsgericht habe in einer Eventualbegründung entschieden, dem Schiedsverfahren stehe die Einrede der res iudicata entgegen. Diese Eventualbegründung habe die Beschwerdeführerin nicht gerügt.
Beruht der angefochtene Entscheid auf mehreren selbständigen Begründungen, die je für sich den Ausgang des Rechtsstreits besiegeln, so hat der Beschwerdeführer darzulegen, dass jede von ihnen Recht verletzt; andernfalls kann auf die Beschwerde nicht eingetreten werden (<ref-ruling> E. 6.3 S. 120 f.; vgl. auch <ref-ruling> E. 2.2 S. 535 f.; Urteil 4A_259/2011 vom 3. August 2011 E. 1.3). Das gilt auch für Beschwerden gegen Schiedsentscheide (Urteil 4P.137/2002 vom 4. Juli 2003 E. 5.1). Wie dargelegt, hat das Schiedsgericht hier aber nur über seine Zuständigkeit entschieden. Über die Prozessvoraussetzung der fehlenden res iudicata hat es ausdrücklich nicht entschieden, sondern sich darüber nur in einem obiter dictum geäussert. Die Frage der res iudicata ist daher nicht Beschwerdegegenstand und es schadet der Beschwerdeführerin nicht, dass sie sich in der Beschwerde dazu nicht geäussert hat.
4.
Die Beschwerdeführerin rügt, das Schiedsgericht habe sich zu Unrecht für unzuständig erklärt (<ref-law>).
4.1. Das Bundesgericht prüft die Zuständigkeitsrüge nach <ref-law> in rechtlicher Hinsicht frei, einschliesslich materieller Vorfragen, von deren Beantwortung die Zuständigkeit abhängt (Urteil 4A_396/2017 vom 16. Oktober 2018 E. 4.1, zur Publikation vorgesehen; <ref-ruling> E. 3.1; <ref-ruling> E. 3.1; <ref-ruling> E. 5 S. 141). Demgegenüber überprüft es die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids auch im Rahmen der Zuständigkeitsrüge nur, wenn gegenüber diesen Sachverhaltsfeststellungen zulässige Rügen im Sinne von <ref-law> vorgebracht oder ausnahmsweise Noven (<ref-law>) berücksichtigt werden (zit. zur Publikation vorgesehenes Urteil 4A_396/2017 E. 4.1; <ref-ruling> E. 3.1, 239 E. 3.1; <ref-ruling> E. 3.1; <ref-ruling> E. 2.2.1; je mit Hinweisen).
4.2. Das Schiedsgericht erwog im Wesentlichen, ob eine gültige Schiedsvereinbarung vorliege, beurteile sich nach türkischem Recht. Art. 504 des türkischen Obligationenrechts ("TCO") bestimme (in nicht bestrittener englischer Übersetzung) : "The agent needs a special authority to (...) consent to arbitration". Dass C._ beim Abschluss des Agenturvertrages über eine solche Spezialvollmacht verfügt habe, sei nicht nachgewiesen. Entgegen der Beschwerdeführerin verstosse die Berufung der Beschwerdegegnerin auf das Fehlen einer speziellen Vollmacht auch nicht gegen Treu und Glauben. So könne sich die Beschwerdegegnerin ohne Weiteres gleichzeitig auf die Gültigkeit des Agenturvertrags berufen und die Gültigkeit der Schiedsvereinbarung als Teil des Agenturvertrags bestreiten. Dies ergebe sich aus dem Grundsatz der Autonomie der Schiedsvereinbarung im Verhältnis zum Hauptvertrag. Auch aus der Tatsache, dass die Beschwerdegegnerin die Gültigkeit der Schiedsvereinbarung nicht bestritten habe im von der Beschwerdeführerin eingeleiteten ersten Schiedsverfahren, das zum Vergleich vom 24. Januar 2010 geführt habe, lasse sich nichts ableiten. Denn dieses sei in einem sehr frühen Verfahrensstadium abgebrochen worden - bevor die Beschwerdegegnerin eine Antwort zum Gesuch der Beschwerdeführerin um Einleitung eines Schiedsverfahrens abgegeben hatte. Daher habe für die Beschwerdegegnerin keine Veranlassung bestanden, auf das Verfahren bezogene Einwände vorzubringen. Das Schiedsgericht verwarf sodann den Einwand der Beschwerdeführerin, mit der Unterzeichnung des Vergleichs vom 24. Januar 2010 habe die Beschwerdegegnerin die Gültigkeit des Agenturvertrages im Nachhinein bestätigt. Die Beschwerdegegnerin habe sich auch im Verfahren vor den katarischen Gerichten nicht widersprüchlich verhalten. Vielmehr habe sie im Gegenteil der Klage der Beschwerdeführerin auf Zahlung zusätzlicher Provisionen gestützt auf den Vergleich vom 24. Januar 2010 nicht die Unzuständigkeit der katarischen Gerichte entgegengehalten. Das türkische Recht verlange eine spezielle Vollmacht; die Beschwerdeführerin könne sich daher auch nicht auf eine Anscheinsvollmacht oder etwas Vergleichbares berufen.
4.3. Die Beschwerdeführerin rügt, entgegen dem Schiedsgericht sei Art. 16 des Agenturvertrags vom 21. April 2007 trotz der behaupteten fehlenden (Spezial-) Vollmacht von C._ gestützt auf Art. 8 und 9 des Vergleichs vom 24. Januar 2010 gültig. In Art. 9 des Vergleichs werde ausdrücklich auf Art. 16 des Agenturvertrages verwiesen. Damit werde die darin enthaltene Schiedsklausel im Sinne eines stillen Verweises unmittelbarer Vertragsbestandteil des Vergleichs. Damit beschränkt die Beschwerdeführerin ihre Rügen zur Gültigkeit der Schiedsklausel auf die Frage, ob die fehlende spezielle Vollmacht für die Vereinbarung einer Schiedsklausel im Agenturvertrag durch den Abschluss des Vergleichs gleichsam geheilt wurde. Auf alle weiteren Argumente des Schiedsgerichts zur Gültigkeit der Schiedsklausel muss daher mangels Rüge nicht (mehr) eingegangen werden.
Nach den Feststellungen des Schiedsgerichts hatte die Beschwerdeführerin geltend gemacht, das Management der Beschwerdegegnerin müsse vom Abschluss des Vergleichs Kenntnis gehabt und so die Gültigkeit der im Vergleich erwähnten Schiedsklausel bestätigt haben. Dem hielt das Schiedsgericht entgegen, im Vergleich werde nicht umfassend auf den Agenturvertrag verwiesen oder die Schiedsklausel bestätigt, sondern alle Streitigkeiten aus dem Vergleich würden an die staatlichen Gerichte Katars verwiesen. Im Hinblick darauf erscheine die Erwähnung der Schiedsklausel im Vergleich als bloss erläuternd und nicht als bindende Bestätigung. Diese (vertrauenstheoretische) Auslegung ist nicht zu beanstanden. Kern von Art. 9 Abs. 2 des Vergleichs ist offensichtlich die Vereinbarung, dass Streitigkeiten aus dem Vergleich durch die staatlichen Gerichte geregelt werden sollen. Der Hinweis auf die Zuständigkeit des Schiedsgerichts für die Streitigkeiten aus dem Agenturvertrag erscheint im Vergleich dazu bloss als (erläuternde) Abgrenzung, was sich insbesondere aus dem Bindewort " whereas"ergibt. Es gibt keine Anhaltspunkte, woraus die Beschwerdeführerin hätte ableiten dürfen, die Beschwerdegegnerin wolle damit die Gültigkeit der Schiedsklausel bestätigen. Die Beschwerdeführerin wendet ein, mit dem Verweis auf eine bloss erläuternde Funktion treffe das Schiedsgericht eine Annahme, die nicht einmal von der Beschwerdegegnerin behauptet worden sei. Sie verkennt, dass es genügt, wenn die Beschwerdegegnerin die Gültigkeit der Schiedsklausel und damit auch die behauptete nachträgliche Genehmigung durch Art. 9 Abs. 2 des Vergleichs bestritt. Damit machte sie geltend, dass dieser Bestimmung nicht jene verpflichtende Bedeutung beigemessen werden kann, welche die Beschwerdeführerin behauptet. Wenn die Beschwerdeführerin schliesslich darauf hinweist, dass es gängiger Übung und Praxis entspreche, auf Bestimmungen oder ganze Vertragswerke zu verweisen, ohne diese wortwörtlich nochmals zu zitieren oder zu wiederholen, ist nicht ersichtlich, was sie daraus ableiten will.
Die Beschwerde ist abzuweisen, ohne dass auf die weitere Begründung des Schiedsgerichts eingegangen werden muss, wonach die vorliegende Streitigkeit ohnehin unter den Vergleich vom 24. Januar 2010 und die darin enthaltene Gerichtsstandsklausel fällt und nicht unter den Agenturvertrag.
5.
Dem Ausgang des Verfahrens entsprechend wird die Beschwerdeführerin kosten- und entschädigungspflichtig (<ref-law> und <ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 40'000.-- werden der Beschwerdeführerin auferlegt.
3.
Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 50'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Schiedsgericht mit Sitz in Zürich schriftlich mitgeteilt.
Lausanne, 27. Februar 2019
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Gross