Sachverhalt:
A.
Die A._ mit Sitz in U._, Ukraine, (Klägerin, Beschwerdegegnerin) ist eine nach ukrainischem Recht gegründete Gesellschaft. Sie erwarb zwischen 2003 und 2006 16 Tankstellen auf der Halbinsel Krim. Zudem mietete sie in der Stadt Feodosia Büroräumlichkeiten, in denen 30 Angestellte arbeiteten. Im Jahre 2013 kontrollierte die Klägerin, nachdem sie weitere Anlagen getätigt hatte, zehn Prozent des Treibstoffmarkts der Krim. Die Krim war damals Teil des ukrainischen Staatsgebiets.
Die Klägerin behauptet, die Russische Föderation (Beklagte, Beschwerdeführerin) habe im Rahmen der Eingliederung der Krim-Halbinsel im Jahre 2014 - am 21. März 2014 wurde der Eingliederungsvertrag ratifiziert und das Integrationsgesetz erlassen - Massnahmen getroffen, welche die erwähnten Vermögenswerte auf der Krim betrafen und zu deren Enteignung führten. Damit habe die Beklagte in verschiedener Hinsicht gegen das Abkommen vom 27. November 1998 (in Kraft seit 27. Januar 2000) z wischen der Regierung der Beklagten und dem Ministerkabinett der Ukraine über die Förderung und den gegenseitigen Schutz von Investitionen (Agreement on the Encouragement and Mutual Protection of Investments, nachfolgend: Investitionsschutzabkommen 1998 bzw. ISA 1998) verstossen und sei daher zu einer Entschädigung verpflichtet.
B.
B.a. Am 3. Juni 2015 leitete die Klägerin gestützt auf Art. 9 des Investitionsschutzabkommens 1998 beim Permanent Court of Arbitration (PCA) ein Schiedsverfahren nach den Arbitration Rules of the United Nations Commission on International Trade Law 1976 (UNCITRAL Rules) gegen die Beklagte ein. Sie beantragte, die Beklagte sei zur Zahlung einer Entschädigung von USD 50'314'336.-- zuzüglich Zins zu verpflichten.
Mit Schreiben ihres Justizministeriums vom 12. August 2015 sowie einem Begleitschreiben ihres Botschafters in den Niederlanden vom 15. September 2015 bestritt die Beklagte die schiedsgerichtliche Zuständigkeit f ür die Beurteilung der geltend gemachten Ansprüche.
Während die Klägerin einen Schiedsrichter bezeichnete, verzichtete die Beklagte darauf, einen solchen zu benennen, weshalb der Generalsekretär des Permanent Court of Arbitration die Bezeichnung eines Schiedrichters verfügte.
Am 7. Oktober 2015 wurde die vorsitzende Schiedsrichterin ernannt.
Am 15. Januar 2016 reichte die Klägerin dem Schiedsgericht ihre begründete Klageschrift ein. Die Beklagte reichte innert der angesetzten Frist keine Antwortschrift ein.
Am 11. Juli 2016 fand in Genf eine mündliche Verhandlung zur Frage der Zuständigkeit statt, an der die Beklagte nicht teilnahm.
Mit Zwischenentscheid vom 26. Juni 2017 ("Award on Jurisdiction") erklärte sich das Schiedsgericht mit Sitz in Genf für zuständig.
Mit Urteil vom 16. Oktober 2018 wies das Bundesgericht eine von der Beklagten gegen den Zwischenentscheid vom 26. Juni 2017 erhobene Beschwerde ab, soweit es darauf eintrat (Verfahren 4A_396/2017).
B.b. Das Schiedsverfahren wurde während des bundesgerichtlichen Beschwerdeverfahrens weitergeführt.
Am 9. August 2017 verabschiedete das Schiedsgericht den Zeitplan für das weitere Verfahren.
Am 21. September 2017 stellte es den Parteien inhaltliche Fragen zur Streitsache.
Mit Eingabe vom 20. November 2017 reichte die Klägerin dem Schiedsgericht ihre Antworten zur materiellen Beurteilung der Sache ein. Die Beklagte verzichtete auf eine Beantwortung der Fragen.
Am 7. Dezember 2017 wurde eine Telefonkonferenz zur Vorbereitung der mündlichen Verhandlung abgehalten. Die Beklagte nahm nicht daran teil.
Am 5./6. Februar 2018 fand in Genf eine mündliche Verhandlung statt. Die Beklagte blieb der Verhandlung fern.
Am 28. Februar 2018 forderte das Schiedsgericht die Parteien auf, sich zur Bestellung des für die Schadensberechnung vorgesehenen Sachverständigen zu äussern.
Die Klägerin reichte dem Schiedsgericht am 6. März 2018 ihre Stellungnahme ein, während die Beklagte auf eine solche verzichtete.
Am 30. Mai 2018 reichte der Gutachter dem Schiedsgericht einen Entwurf seines Gutachtens ein.
Die Klägerin äusserte sich dazu am 3. Juli 2018. Die Beklagte verzichtete auf eine Stellungnahme.
Am 16. Juli 2018 reichte der Sachverständige die endgültige Fassung seines Gutachtens ein, die den Parteien am nächsten Tag zugestellt wurde.
Am 20. Juli 2018 äusserte sich die Klägerin zum Gutachten, während die Beklagte dazu nicht Stellung bezog.
Am 20. August 2018 fand in Genf eine mündliche Verhandlung statt. Die Beklagte nahm daran nicht teil.
Am 13. Oktober 2018 reichte der Sachverständige dem Schiedsgericht eine Ergänzung des Gutachtens ein, zu der sich die Klägerin am 23. Oktober 2018 äusserte, während die Beklagte auf eine Stellungnahme verzichtete.
B.c. Mit Schiedsentscheid vom 12. April 2019 stellte das Schiedsgericht mit Sitz in Genf fest, die Beklagte habe in Bezug auf die Investitionen der Klägerin Art. 5 des Investitionsschutzabkommens 1998 verletzt und verurteilte sie zur Zahlung von Schadenersatz im Betrag von USD 44'455'012.-- an die Klägerin, zuzüglich Zins seit 22. April 2014.
Das Schiedsgericht erwog, die Beklagte habe die von der Klägerin getätigten Investitionen in Form von 16 Tankstellen in Verletzung von Art. 5 des Investitionsschutzabkommens 1998 enteignet. Dafür schulde die Beklagte eine Entschädigung im aufgeführten Betrag.
C.
Mit Beschwerde in Zivilsachen beantragt die Beklagte dem Bundesgericht, es sei die vollständige, eventualiter die teilweise Nichtigkeit des Schiedsentscheids des Schiedsgerichts mit Sitz in Genf vom 12. April 2019 festzustellen. Eventualiter sei der angefochtene Schiedsentscheid aufzuheben. Gleichzeitig ersuchte sie um Gewährung der aufschiebenden Wirkung.
Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Schiedsgericht hat auf eine Vernehmlassung verzichtet.
Die Parteien haben repliziert und dupliziert.
D.
Mit Verfügung vom 31. Mai 2019 hat das Bundesgericht auf die von der Beschwerdeführerin beantragte superprovisorische Erteilung der aufschiebenden Wirkung verzichtet.

Erwägungen:
1.
Die Beschwerdeführerin beantragt, es sei das vorliegende Verfahren mit dem Beschwerdeverfahren 4A_246/2019 betreffend den Schiedsentscheid des Schiedsgerichts mit Sitz in Genf vom 12. April 2019 im Schiedsverfahren PCA Nr. xxx zu vereinigen. Den Verfahren 4A_244/2019 und 4A_246/2019 liegen zwar vergleichbare Sachverhalte zugrunde, die Beschwerden richten sich jedoch nicht gegen denselben Entscheid und an den jeweiligen Schiedsverfahren sind nicht dieselben Parteien beteiligt, weshalb auf eine Vereinigung der beiden Beschwerdeverfahren verzichtet wird.
2.
Nach <ref-law> ergeht der Entscheid des Bundesgerichts in einer Amtssprache, in der Regel in jener des angefochtenen Entscheids. Wurde dieser Entscheid in einer anderen Sprache abgefasst, bedient sich das Bundesgericht der von den Parteien verwendeten Amtssprache. Verwenden die Parteien nicht die gleiche Amtssprache, ergeht der Entscheid des Bundesgerichts praxisgemäss in der Sprache der Beschwerde (<ref-ruling> E. 1).
Im vorliegenden Fall, in dem die Beschwerdeführerin ihre Beschwerde auf Französisch und die Beschwerdegegnerin ihre Rechtsschriften auf Deutsch eingereicht hat, ist jedoch zu berücksichtigen, dass die Beschwerdeführerin im gleichen Schiedsverfahren bereits den schiedsgerichtlichen Zwischenentscheid über die Zuständigkeit mit Beschwerde beim Bundesgericht anfocht, wobei sie die Beschwerde auf Deutsch einreichte (Urteil 4A_396/2017 vom 16. Oktober 2018 E. 2). Dabei war sie bereits damals von den beiden Rechtsanwälten vertreten, die im vorliegenden Verfahren die Beschwerdeschrift eingereicht haben. Als Ausnahme von der aufgeführten Praxis ergeht der Entscheid des Bundesgerichts daher wie im vorangehenden Beschwerdeverfahren auf Deutsch.
3.
Im Bereich der internationalen Schiedsgerichtsbarkeit ist die Beschwerde in Zivilsachen unter den Voraussetzungen der Art. 190-192 IPRG (SR 291) zulässig (<ref-law>).
3.1. Der Sitz des Schiedsgerichts befindet sich vorliegend in Genf. Die Parteien hatten im massgebenden Zeitpunkt 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>).
3.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).
3.3. Die Beschwerde ist innert der Beschwerdefrist vollständig begründet einzureichen (<ref-law>). Kommt es zu einem zweiten Schriftenwechsel, darf die beschwerdeführende Partei die Replik nicht dazu verwenden, ihre Beschwerde zu ergänzen oder zu verbessern (vgl. <ref-ruling> E. 3.3.4). Die Replik ist nur zu Darlegungen zu verwenden, zu denen die Ausführungen in der Vernehmlassung eines anderen Verfahrensbeteiligten Anlass geben (vgl. <ref-ruling> E. 2.2).
Soweit die Beschwerdeführerin in ihrer Replik darüber hinausgeht, können ihre Ausführungen nicht berücksichtigt werden.
3.4. 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.5. Diese Grundsätze verkennt die Beschwerdeführerin, wenn sie vor Bundesgericht unter Hinweis auf zahlreiche neu eingereichte Unterlagen verschiedenste Behauptungen zu Herrn B._ - einem bedeutenden Minderheitsaktionär der Beschwerdegegnerin - aufstellt und daraus ableitet, er sei durch betrügerische Machenschaften und Korruption zu seinem Vermögen gekommen. Von notorischen Tatsachen, die vom Bundesgericht zu berücksichtigen wären, obwohl sie im angefochtenen Entscheid nicht festgestellt wurden, kann entgegen der in der Beschwerde vertretenen Ansicht keine Rede sein (vgl. zu den vom Novenverbot nach <ref-law> nicht erfassten allgemein bekannten und gerichtsnotorischen Tatsachen etwa Urteile 9C_748/2014 vom 14. April 2015 E. 2.1; 4A_560/2012 vom 1. März 2013 E. 2.2). Zudem lässt sich weder aus dem in der Beschwerde ins Feld geführten Umstand, dass die Beschwerdegegnerin im Schiedsverfahren darauf verzichtete, entsprechende Tatsachen vorzutragen, noch mit dem blossen Hinweis auf abweichende Verfahrensregeln einer ausländischen Rechtsordnung etwas zugunsten der Beschwerdeführerin ableiten. Es wäre im Gegenteil an der Beschwerdeführerin gewesen, diese Tatsachen rechtzeitig im Schiedsverfahren geltend zu machen. Darauf hatte sie jedoch bewusst verzichtet. Mit dem erst vor Bundesgericht erhobenen Einwand, die fraglichen Investitionen seien unter betrügerischen Umständen zustande gekommen, ist sie nicht zu hören, weshalb die darauf gestützte Rüge der Verletzung des Ordre public nach <ref-law> von vornherein ins Leere stösst.
4.
Die Beschwerdeführerin bringt vor, der angefochtene Schiedsentscheid sei mangels Schiedsfähigkeit der Streitsache nichtig oder zumindest anfechtbar.
4.1. Das Schiedsgericht halte im angefochtenen Entscheid fest, dass die Streitigkeit vom räumlichen und zeitlichen Anwendungsbereich des Investitionsschutzabkommens 1998 erfasst sei und die Klägerin eine Investition in Russland getätigt habe. Mit anderen Worten gehe es davon aus, dass die Krim ab einem bestimmten Datum (d.h. ab 21. März 2014) ihren Status in Bezug auf das ISA 1998 geändert habe. Der Entscheid des Schiedsgerichts über den Status der Krim habe rechtliche Konsequenzen für die Parteien wie auch für die Ukraine gehabt, indem er die Verpflichtungen der Vertragsstaaten des Abkommens fundamental geändert habe, ohne dass diese jedoch eine formelle Abänderung nach Art. 13 ISA 1998 oder eine stillschweigende Anpassung vorgenommen hätten. Bezeichnenderweise habe sich die Ukraine am Schiedsverfahren beteiligen wollen, was für die Bedeutung des Entscheids für die Vertragsstaaten des ISA 1998 spreche. Der Status der Krim in Bezug auf das Abkommen bzw. die Änderung dieses Status sei eine Frage, die weder von der Beschwerdegegnerin als privater juristischer Person noch von einer Vertragspartei des Abkommens im Alleingang bestimmt werden könne. Vielmehr erlaube Art. 13 ISA 1998 einzig den Vertragsstaaten, den Umfang ihrer gegenseitigen Verpflichtungen auf dem Weg einer formellen Vertragsänderung in dem dafür vorgesehenen Verfahren zu bestimmen.
Im zu beurteilenden Fall habe das Schiedsgericht über einen Gegenstand - den Status der Krim in Bezug auf das ISA 1998 - entschieden, der die Verpflichtungen der Vertragsstaaten fundamental ändere, seiner Natur nach nicht in einem Schiedsverfahren zwischen der Beschwerdegegnerin und der Beschwerdeführerin entschieden werden könne und keinen vermögensrechtlichen Anspruch im Sinne von <ref-law> darstelle. Bei der Frage des Status der Krim, d.h. ob diese in Bezug auf das ISA 1998 als ukrainisches oder russisches Territorium zu betrachten sei, handle es sich zudem weder lediglich um eine vom Schiedsgericht zu beantwortende Vorfrage noch um eine blosse Auslegung des I nvestitionsschutzabkommens 1998 durch das Schiedsgericht. Vielmehr handle es sich um nicht mehr und nicht weniger als eine Beantwortung der Frage, ob sich die Verpflichtungen der Vertragsstaaten nach der Eingliederung der Krim in die Russische Föderation geändert haben. Das Schiedsgericht habe sich angemasst, über eine Frage zu entscheiden, die weder frei zwischen einem Vertragsstaat und einem Privaten bestimmbar noch im Sinne von <ref-law> schiedsfähig sei. Der angefochtene Entscheid sei deshalb - zumindest teilweise - nichtig zu erklären, indem er anordne, dass die Krimhalbinsel ab einem bestimmten Datum ihr Wesen in Bezug auf das ISA 1998 geändert habe. Eventualiter sei er infolge Verletzung des Ordre public (<ref-law>) aufzuheben.
4.2. Entgegen dem, was die Beschwerdeführerin anzunehmen scheint, war Streitgegenstand des Schiedsverfahrens nicht der Status der Krim in Bezug auf das Investitionsschutzabkommen 1998 oder deren völkerrechtlicher Status, sondern vielmehr der von der Beschwerdegegnerin eingeklagte Anspruch auf Entschädigungszahlungen im Betrag von USD 50'314'336.-- zuzüglich Zins infolge angeblich vertragswidriger Enteignung ihrer Investitionen durch die Beschwerdeführerin. Dabei handelt es sich zweifellos um einen vermögensrechtlichen Anspruch im Sinne von <ref-law>. Der Einwand der fehlenden Schiedsfähigkeit der Streitsache ist haltlos, weshalb das Vorbringen der Beschwerdeführerin bereits aus diesem Grund ins Leere stösst. Entgegen der in der Beschwerde vertretenen Ansicht ist der angefochtene Entscheid - wegen angeblich mangelnder Schiedsfähigkeit - weder nichtig noch anfechtbar. Es braucht daher nicht vertieft zu werden, ob der erst in der Beschwerde gegen den Endentscheid erhobene Einwand überhaupt geprüft werden kann, was von der Beschwerdegegnerin bestritten wird (vgl. dazu <ref-ruling> E. 3.2.2.1 S. 586 f.).
Richtig besehen bestreitet die Beschwerdeführerin einmal mehr die schiedsgerichtliche Zuständigkeit, indem sich ihre Ausführungen gegen eine Erwägung im angefochtenen Entscheid richten, mit der das Schiedsgericht lediglich aus seinem Zwischenentscheid über die Zuständigkeit vom 26. Juni 2017 zitierte (Ziff. 41: "In concluding that it had jurisdiction over the present dispute, the Tribunal held [in the Award on Jurisdiction of 12 April 2019] that 'the dispute falls within the territorial and temporal scope of application of the Treaty and that the Claimant qualifies as an 'investor' under the Treaty, having made an 'investment' in the territory of Russia in accordance with its legislation."). Das Bundesgericht hat über die Zuständigkeit des Schiedsgerichts jedoch bereits mit Urteil 4A_396/2017 vom 16. Oktober 2018 entschieden (<ref-ruling>), indem es die von der Beschwerdeführerin gegen den schiedsgerichtlichen Zwischenentscheid erhobene Beschwerde abwies, soweit es darauf eintrat. Das Bundesgericht hat dabei die Rüge, wonach eine Berücksichtigung nachfolgender Grenzverschiebungen eine weitere Vereinbarung der Vertragsparteien nach Art. 13 ISA 1998 vorausgesetzt hätte, als unbegründet erachtet; es hat zudem ausdrücklich festgehalten, das Schiedsgericht sei zu Recht davon ausgegangen, dass das Gebiet der Halbinsel Krim als Teil des "Territoriums" der Beschwerdeführerin im Sinne von Art. 1 Abs. 4 ISA 1998 zu betrachten sei und vom räumlichen Geltungsbereich des Abkommens erfasst werde (<ref-ruling> E. 4.3.2). Nachdem das Bundesgericht bereits rechtskräftig darüber entschieden hat, kann die schiedsgerichtliche Zuständigkeit nicht mehr mit Beschwerde gegen den Endentscheid in Frage gestellt werden.
Der in der Beschwerde erhobene Einwand, der angefochtene Schiedsentscheid sei mangels Schiedsfähigkeit der Streitsache nichtig oder - infolge Ordre public-Widrigkeit - zumindest anfechtbar, stösst ins Leere.
5.
Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Mit dem Entscheid in der Sache wird das Gesuch um aufschiebende Wirkung gegenstandslos.
Dem Ausgang des Verfahrens entsprechend wird die Beschwerdeführerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

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