Sachverhalt: A. A.a. A._ A.S. (Klägerin, Beschwerdeführerin) ist eine nach türkischem Recht gegründete Gesellschaft mit Sitz in U._, Türkei. Alleinaktionär ist C._. B._ Co. Ltd. (Beklagte, Beschwerdegegnerin) ist eine Gesellschaft irakischen Rechts mit Sitz in V._, Irak. A.b. Am 15. Mai 2013 unterzeichneten C._ und D._ einen Aktionärbindungsvertrag ("Shareholders Agreement") hinsichtlich der Beteiligung an der B._ Co. Ltd. Dabei unterzeichnete C._ den Vertrag im Namen der Aktionärin A._ A.S. Umstritten ist, ob D._ den Vertrag ausschliesslich in eigenem Namen, d.h. als Aktionär der B._ Co. Ltd., abschloss oder zusätzlich auch im Namen der B._ Co. Ltd. selbst. Artikel 16.2 des Aktionärbindungsvertrags lautet wie folgt: "Any dispute, controversy or claim arising out of or in connection with this Agreement, including its conclusion, validity, binding effect, amendment, breach, termination or rescission and including any Disputes concerning the jurisdiction of the arbitral tribunal or the scope of arbitral issues, which is not settled amicably within thirty (30) days shall be finally and exclusively referred to and settled by arbitration by three (3) arbitrator appointed in accordance with the Rules of Arbitration (the "Rules") of the International Chamber of Commerce ("ICC") in effect at the time of the arbitration. Each Party shall designate one (1) arbitrator and two (2) arbitrators so selected or designated shall choose a neutral third arbitrator who shall also act as the chairman of the arbitration panel. The following shall apply to any arbitration pursuant to this Article: a. The seat of the arbitration shall be Geneva/Switzerland. b. The English language shall be used as the written and spoken language for the arbitration and all matters connected to the arbitration. c. The arbitrator shall have the power to (i) render a declaratory judgment; (ii) award specific performance or injunctive relief; (iii) award damages; (iv) award reasonable attorney's fees and expenses to any party in the arbitration; and (v) grant such other relief as they deem necessary to resolve the applicable Dispute. d. The service of any demand, notice, process, motion or other document in connection with any arbitration or related court action or proceeding shall be effectuated by personal service upon the Parties at their respective addresses indicated under this Agreement (and such service shall be deemed to have occurred at the time of delivery)." Am 28. Juli 2013 verkaufte D._ seine Aktien an der B._ Co. Ltd. an E._. Am 10. Juli 2013 unterzeichneten C._ und E._ ein Protokoll zum Aktionärbindungsvertrag vom 15. Mai 2013. Dabei ist unbestritten, dass das Protokoll zwischen A._ A.S. (vertreten durch C._) und E._ abgeschlossen wurde, dem neuen zweiten Aktionär der B._ Co. Ltd. Nach dem Wortlaut des Protokolls soll damit Artikel 5 des Aktionärbindungsvertrags (betreffend den Verwaltungsrat) abgeändert werden, während dessen übrige Bestimmungen weiterhin gelten sollen. Im September 2013 erarbeiteten die Beteiligten den Entwurf eines revidierten Protokolls ("Revised Protocol"), das in der Folge jedoch nicht unterzeichnet wurde. Am 3. November 2013 fand in V._, Irak, ein Treffen zwischen E._ und C._ statt. Das entsprechende Gesprächsprotokoll wurde von E._ als Präsident und von C._ als Vizepräsident der B._ Co. Ltd. unterzeichnet. Ebenfalls am 3. November 2013 unterzeichneten C._ und E._ eine revidierte Version des Protokolls vom 10. Juli 2013. Damit wurde wiederum Artikel 5 des Aktionärbindungsvertrags abgeändert, während die übrigen Bestimmungen unverändert gelten sollen. Im Gegensatz zum Protokoll vom 10. Juli 2013 sind auf demjenigen vom 3. November 2013 neben den Unterschriften von C._ und E._ die beiden Firmenstempel der A._ A.S. und der B._ Co. Ltd. angebracht. Die Parteien sind sich uneinig, wie und zu welchem Zweck die Stempel auf dem Protokoll angebracht wurden. B. B.a. Am 16. Januar 2015 leitete die A._ A.S. ein Schiedsverfahren nach den Bestimmungen der Internationalen Handelskammer (ICC) gegen E._ und B._ Co. Ltd. ein. Sie beantragte unter anderem, diese hätten ihr USD 34'034'000.-- zu bezahlen und es seien vorsorgliche Massnahmen anzuordnen. Dabei stützte sich die Klägerin nicht nur auf den Aktionärbindungsvertrag vom 15. Mai 2013 und das Protokoll vom 3. November 2013, sondern auch auf das Code Share Agreement vom 1. September 2013 und das Total Maintenance Support Services Agreement vom 31. Dezember 2013, obwohl diese beiden Vereinbarungen je eigene Bestimmungen zur Streitentscheidung enthalten. Neben E._ erhob auch die Beklagte Einwände gegen die Zuständigkeit des Schiedsgerichts; dies in erster Linie mit der Begründung, sie sei weder Partei des Aktionärbindungsvertrags vom 15. Mai 2013 noch des Protokolls vom 3. November 2013. Am 11. Juni 2015 bestätigte der ICC-Gerichtshof die beiden von den Parteien ernannten Schiedsrichter. Diese bestellten gemeinsam den Schiedsobmann, der am 3. Juli 2015 vom Generalsekretär des ICC-Gerichtshofs bestätigt wurde. B.b. Mit Schiedsentscheid ( "Partial Award") vom 11. April 2016 erklärte sich das ICC Schiedsgericht mit Sitz in Genf für unzuständig, soweit das Verfahren die Beklagte betrifft (Dispositiv-Ziffer 1). Im Weiteren stellte es fest, für die Beurteilung der Klage nicht zuständig zu sein, soweit sie sich auf das Code Share Agreement oder das Total Maintenance Support Services Agreement stütze (Dispositiv-Ziffer 2). Es verpflichtete die Klägerin zudem zur Zahlung einer Parteientschädigung von USD 290'706.06, zuzüglich Zins zu 5 % (Dispositiv-Ziffer 3). C. Mit Beschwerde in Zivilsachen, in der einzig die Beklagte als Beschwerdegegnerin aufgeführt wird, beantragt die Beschwerdeführerin dem Bundesgericht, es sei der Schiedsentscheid des ICC Schiedsgerichts mit Sitz in Genf vom 11. April 2016 aufzuheben und es sei festzustellen, dass die subjektive Tragweite der Schiedsvereinbarung und mithin die Zuständigkeit des Schiedsgerichts auch die Beklagte umfasse. Zudem "sei festzustellen, dass die objektive Tragweite der Schiedsvereinbarung und mithin die Zuständigkeit des Schiedsgerichts alle Klagen umfasst, welche sich aus dem (möglichen) Bruch des Hauptvertrages ('Shareholders Agreement' vom 15. Mai 2013) zusammen mit dem Protokoll als integralem Bestandteil ('Protocol' vom 3. November 2013) ergeben. Dies insbesondere auch dann, wenn diese Klagen zusätzlich in Verbindung mit anderen Vereinbarungen, namentlich dem Code Share Agreement vom 1. September 2013 und dem Total Maintenance Support Services Agreement vom 31. Dezember 2012 [gemeint: 2013], stehen". Die Beschwerdegegnerin beantragt, es sei auf die Beschwerde nicht einzutreten; eventualiter sei sie abzuweisen. Das Schiedsgericht hat auf eine Vernehmlassung verzichtet. Die Beschwerdeführerin hat dem Bundesgericht eine Replik, die Beschwerdegegnerin hat ihm eine Duplik eingereicht. D. Mit Verfügung vom 4. August 2016 erteilte das Bundesgericht der Beschwerde mit Bezug auf Dispositiv-Ziffer 3 des angefochtenen Schiedsentscheids die aufschiebende Wirkung. Im Mehrumfang lehnte es das Gesuch der Beschwerdeführerin um aufschiebende Wirkung ab.