Citation: 4A_305/2013 E. 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.