Sachverhalt:
A.
A.a. Die X._ AG (Beschwerdeführerin 1) ist eine Kapitalgesellschaft deutschen Rechts mit Sitz in R._.
Die X._ Technologies S.A.E. (Beschwerdeführerin 2) ist eine Kapitalgesellschaft nach dem Recht der Arabischen Republik Ägypten mit Sitz Ägypten.
Die Y._ (Beschwerdegegnerin) ist eine Gesellschaft nach dem Recht der Arabischen Republik Ägypten mit Sitz in Ägypten.
Die Beschwerdegegnerin gehört zusammen mit der Z_ zum ägyptischenKonzern Q._.
A.b. Am 18. Februar 1999 schlossen die Beschwerdeführerinnen mit der Beschwerdegegnerin einen exklusiven Vertriebsvertrag ab ("Distribution Agreement 1999"), auf dessen Grundlage die Beschwerdegegnerin von 1999 bis 2003 als Vertriebspartnerin der Beschwerdeführerin 1 in Ägypten tätig war.
Das "Distribution Agreement 1999"enthält in Artikel 18 eine Schiedsklausel.
Am 25. November 2003 beendeten die Parteien das "Distribution Agreement 1999" mittels einer Aufhebungsvereinbarung. In der Folge schlossen die Beschwerdeführerinnen mit der Z._ ein neues "Distribution Agreement 2003" ab, welches das aufgehobene "Distribution Agreement 1999" mit der Beschwerdegegnerin ablöste.
Im Jahr 2004 schlossen die Beschwerdeführerinnen und die Z._ eine Nebenabrede ("Side Letter 2004" ) ab, in der sich die Z._ verpflichtete, die vollumfängliche Verantwortung für "all commitments, obligations and litigations out of the business of Y._ " zu übernehmen.
Im Jahr 2006 schlossen die Beschwerdeführerinnen und die Z._ ein neues "Distribution Agreement 2006" ab, das anders als die vorherigen Vertriebsverträge nicht exklusiv war. Parallel hierzu wurde ein Vergleichsvertrag ("Settlement Agreement 2006") abgeschlossen, in dem sich die Z._ verpflichtete, diverse vor ägyptischen Gerichten gegen die Beschwerdeführerinnen anhängig gemachte Klagen gegen Bezahlung eines bestimmten Betrags zurückzuziehen. Die Beschwerdeführerinnen leisteten die entsprechende Zahlung jedoch nicht.
A.c. In der Folge reichte die Beschwerdegegnerin bei staatlichen ägyptischen Gerichten mehrere Klagen ein, mit denen sie gegenüber den Beschwerdeführerinnen Ansprüche aus dem "Distribution Agreement 1999" geltend machte. Die Beschwerdeführerinnen erhoben in diesen Verfahren die Schiedseinrede.
B.
Um sich gegen die wiederholten Klagen der Beschwerdegegnerin in Ägypten unter dem "Distribution Agreement 1999" zur Wehr zu setzen, leiteten die Beschwerdeführerinnen am 13. Januar 2011 bei der ICC ein Schiedsverfahren ein mit dem Begehren, es sei festzustellen, dass der Beschwerdegegnerin unter dem "Distribution Agreement 1999" und/oder im Zusammenhang mit dessen Beendigung keinerlei Ansprüche zustehen.
Die Beschwerdegegnerin bestritt die Zuständigkeit des Schiedsgerichts.
Mit Schiedsspruch vom 6. Mai 2013 verneinte das Schiedsgericht seine Zuständigkeit zur Beurteilung der von den Beschwerdeführerinnen gegen die Beschwerdegegnerin eingereichten Schiedsklage.
C.
Mit Beschwerde in Zivilsachen stellen die Beschwerdeführerinnen dem Bundesgericht folgende Rechtsbegehren:
"1. Es sei der Schiedsspruch vom 6. Mai 2013 im Schiedsverfahren Nr. 17680/FM/MHM/EMT vor der International Chamber of Commerce aufzuheben und festzustellen, dass das Schiedsgericht zur Beurteilung der Schiedsklage der Beschwerdeführerinnen zuständig ist, mit Ausnahme der Rechtsbegehren Nr. 2. 3 und 4 der Beschwerdeführerinnen gemäss Terms of Reference;
2. Es sei das Verfahren mit Ausnahme der Rechtsbegehren Nr. 2, 3 und 4 der Beschwerdeführerinnen gemäss Terms of Reference zur materiellen Beurteilung der Schiedsklage an das Schiedsgericht zurückzuweisen;
3. Eventualiter sei das Verfahren zur weiteren Prüfung der Zuständigkeit an das Schiedsgericht zurückzuweisen;
4. Unter Kosten- und Entschädigungsfolgen zu Lasten der Beschwerdegegnerin."
Es wurden keine Vernehmlassungen eingeholt.

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 Beschwerdeführerinnen 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. Beide Parteien hatten im relevanten Zeitpunkt ihren Sitz ausserhalb der Schweiz. Da die Parteien die Bestimmungen des 12. Kapitels des IPRG nicht schriftlich ausgeschlossen haben, gelangen diese zur Anwendung (Art. 176 Abs. 1 und 2 IPRG).
2.2. 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.3. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den das Schiedsgericht festgestellt hat (<ref-law>). Es 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 der Vorinstanz beruft und den Sachverhalt gestützt darauf berichtigt oder ergänzt wissen will, hat mit Aktenhinweisen darzulegen, dass entsprechende Sachbehauptungen bereits im vorinstanzlichen Verfahren prozesskonform aufgestellt worden sind (vgl. <ref-ruling> E. 2a S. 486; <ref-ruling> E. 1c S. 473; je mit Hinweisen).
3.
Die Beschwerdeführerinnen rügen unter Anrufung von <ref-law>, dass sich das Schiedsgericht zu Unrecht für unzuständig erklärt habe. Dieses sei aufgrund einer normativen Auslegung zweier Vertragsbestimmungen, welche zwischen den Beschwerdeführerinnen und der Z._ als Drittpartei im "Side Letter 2004" bzw. im "Settlement Agreement 2006" vereinbart wurden, zum Schluss gelangt, die Parteien hätten das "Distribution Agreement 1999" vollumfänglich, d.h. inklusive Schiedsklausel beendet. Diese Konstruktion eines normativen Konsenses durch das Schiedsgericht sei unhaltbar und verletze den Grundsatz der Autonomie der Schiedsklausel. Die Äusserungen und Handlungen der Parteien würden vielmehr gerade belegen, dass die Parteien auch nach Beendigung des "Distribution Agreement 1999" an der Weitergeltung der Schiedsklausel festhalten wollten.
3.1. Das Bundesgericht prüft die Zuständigkeitsrüge nach <ref-law> einschliesslich materieller Vorfragen, von deren Beantwortung die Zuständigkeit abhängt, in rechtlicher Hinsicht frei. 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 berücksichtigt werden (<ref-ruling> E. 2.2.1 S. 34; <ref-ruling> E. 3.1 S. 567; <ref-ruling> E. 5 S. 141).
3.2.
3.2.1. Eine Schiedsvereinbarung ist eine Übereinkunft, mit der sich zwei oder mehrere bestimmte oder bestimmbare Parteien einigen, eine oder mehrere, bestehende oder künftige Streitigkeiten verbindlich unter Ausschluss der ursprünglichen staatlichen Gerichtsbarkeit einem Schiedsgericht nach Massgabe einer unmittelbar oder mittelbar bestimmten rechtlichen Ordnung zu unterstellen (<ref-ruling> E. 2.2.3 S. 35 mit Hinweisen).
Ist eine Schiedsvereinbarung zustande gekommen, kann diese jederzeit, d.h. insbesondere auch während des hängigen Schiedsverfahrens, durch formlose gegenseitige Übereinkunft wieder aufgehoben werden ( POUDRET/BESSON, Comparative law of international arbitration, 2. Aufl. 2007, Rz. 379; BERGER/KELLERHALS, International and Domestic Arbitration in Switzerland, 2. Aufl. 2010, Rz. 556; Pierre-Yves Tschanz, in: Commentaire romand, 2011, N. 181 zu <ref-law>; Kaufmann-Kohler/Rigozzi, Arbitrage international, 2. Aufl. 2010, Rz. 273). Diesfalls entfällt die Zuständigkeit des Schiedsgerichts.
3.2.2. Die Auslegung einer Schiedsvereinbarung folgt den für die Auslegung privater Willenserklärungen allgemein geltenden Grundsätzen. Massgebend ist danach in erster Linie der übereinstimmende tatsächliche Wille der Parteien. Diese subjektive Vertragsauslegung beruht auf Beweiswürdigung (<ref-ruling> E. 3.1 S. 632 m.H.). Stellt die Vorinstanz einen von einem übereinstimmenden wirklichen Parteiwillen getragenen Vertragsinhalt fest, so handelt es sich dabei um eine Sachverhaltsfeststellung, welche für das Bundesgericht grundsätzlich verbindlich ist (<ref-law>).
Nur wenn ein übereinstimmender tatsächlicher Wille nicht festgestellt werden kann, ist die Schiedsvereinbarung objektiviert auszulegen, d.h. der mutmassliche Parteiwille ist so zu ermitteln, wie er vom jeweiligen Erklärungsempfänger nach den gesamten Umständen in guten Treuen verstanden werden durfte und musste (<ref-ruling> E. 2.2.3; <ref-ruling> E. 3.2 S. 71). Dabei ist der Zeitpunkt des Vertragsschlusses massgebend, weshalb bei der Auslegung nach dem Vertrauensprinzip nachträgliches Parteiverhalten nicht von Bedeutung ist (<ref-ruling> E. 2.3 S. 680 mit Hinweis).
3.3. Nach Auffassung des Schiedsgerichts beweisen ("evidence") die nach der Aufhebung des "Distribution Agreement 1999" abgeschlossenen Vereinbarungen, dass die Parteien das "Distribution Agreement 1999" vollumfänglich, d.h. einschliesslich der Schiedsklausel beenden wollten. Das Schiedsgericht weist darauf hin, dass sowohl der "Side Letter 2004" als auch das "Settlement Agreement 2006" eine Passage enthalten, wonach sämtliche Vereinbarungen zwischen der Beschwerdegegnerin und den Vertragsparteien in Kraft blieben mit Ausnahme des "Distribution Agreement 1999" ("All previous agreements, except for the Distribution Agreement dated February 18, 1999, between Y._ and the Parties and/or End-users of Contractual Products in Egypt remain in force and will be adhered to by the Distributor without limitations"). Die doppelte Wiederholung der Feststellung, wonach das "Distribution Agreement 1999" beendet sei, sowie der Verzicht auf einen Vorbehalt zugunsten der Weitergeltung der Schiedsklausel beweisen nach Auffassung des Schiedsgericht einen übereinstimmenden Willen ("joint intent") der Beschwerdeführerinnen und der Beschwerdegegnerin bzw. deren Konzernschwester Z._, das "Distribution Agreement 1999" einschliesslich der Schiedsklausel zu beenden.
3.4. Entgegen der Auffassung der Beschwerdeführerinnen handelt es sich bei diesen Ausführungen des Schiedsgerichts nicht um eine normative, sondern um eine subjektive Vertragsauslegung. Die Vorinstanz hat gestützt auf nachträgliches Parteiverhalten beweiswürdigend auf einen tatsächlich übereinstimmenden Willen der Parteien im Moment des Abschlusses der Aufhebungsvereinbarung geschlossen. Dies ergibt sich aus der eindeutigen Formulierung der Erwägungen, wonach das nachträgliche Parteiverhalten einen "übereinstimmenden Willen" ("joint intent") "beweise" ("evidence"), sowie dem Umstand, dass nachträgliches Parteiverhalten bei einer Auslegung nach dem Vertrauensprinzip nicht von Bedeutung ist. Beim Schluss des Schiedsgerichts, wonach die im "Distribution Agreement 1999" enthaltene Schiedsvereinbarung durch tatsächlichen Konsens aufgehoben worden sei, handelt es sich mithin um eine Sachverhaltsfeststellung, welche für das Bundesgericht verbindlich ist (<ref-law>).
Dagegen bringen die Beschwerdeführerinnen keine zulässigen Rügen vor, indem sie lediglich die - hier nicht erfolgte - normative Auslegung der Aufhebungsvereinbarung als unrichtig rügen; bezogen auf die vorinstanzliche Sachverhaltsfeststellung erweisen sich die entsprechenden Vorbringen der Beschwerdeführerinnen als blosse appellatorische Kritik bzw. als im Rahmen einer Schiedsbeschwerde nach <ref-law> unzulässige Kritik an der vorinstanzlichen Beweiswürdigung. Dies gilt auch, soweit die Beschwerdeführerinnen eine angebliche "Missachtung des Grundsatzes der Autonomie der Schiedsvereinbarung " rügen. Darauf ist nicht einzutreten.
4.
Die Beschwerdeführerinnen rügen weiter eine Verletzung ihres rechtlichen Gehörs (<ref-law>) durch überraschende Rechtsanwendung, indem das Schiedsgericht den Grundsatz der Autonomie der Schiedsklausel " neu interpretiert" sowie einen "normativen Konsens" konstruiert habe, ohne dass die Beschwerdeführerinnen dazu angehört worden seien.
Auch diese Rüge gründet auf der unzutreffenden Annahme, dass die Vorinstanz eine Aufhebung der Schiedsvereinbarung durch normativen Konsens angenommen hat. Die Vorinstanz hat weder den Grundsatz der Autonomie der Schiedsklausel neu interpretiert noch einen normativen Konsens konstruiert, sondern beweiswürdigend auf einen tatsächlich übereinstimmenden Willen zur Aufhebung der Schiedsvereinbarung geschlossen. Darin liegt keine überraschende Rechtsanwendung. Soweit die Beschwerdeführerinnen sinngemäss auch eine "überraschende Beweiswürdigung" rügen wollen, verkennen sie schliesslich, dass die vom Bundesgericht entwickelten Grundsätze zur überraschenden Rechtsanwendung keine analoge Anwendung auf die Beweiswürdigung finden (Urteile 4A_214/2013 vom 5. August 2013 E. 4.1, 4.3.1; 4A_538/2012 vom 17. Januar 2013 E. 5.1). Die Vorbringen der Beschwerdeführerinnen erweisen sich somit auch hier als im Rahmen einer Schiedsbeschwerde nach <ref-law> unzulässige Kritik an der vorinstanzlichen Beweiswürdigung, auf die nicht einzutreten ist.
5.
Auf die Beschwerde ist nicht einzutreten.
Bei diesem Ausgang des Verfahrens werden die Beschwerdeführerinnen unter solidarischer Haftbarkeit kostenpflichtig (<ref-law>). Der Beschwerdegegnerin ist aus dem bundesgerichtlichen Verfahren kein Aufwand entstanden, weshalb ihr keine Parteientschädigung zusteht.

Demnach erkennt das Bundesgericht:
1.
Auf die Beschwerde wird nicht eingetreten.
2.
Die Gerichtskosten von Fr. 20'000.-- werden den Beschwerdeführerinnen unter solidarischer Haftbarkeit und intern zu gleichen Teilen auferlegt.
3.
Dieses Urteil wird den Parteien und dem ICC Schiedsgericht mit Sitz in Zürich schriftlich mitgeteilt.
Lausanne, 2. Oktober 2013
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Hurni