Sachverhalt:
A. Die X._ AG mit Sitz in Baden (Beschwerdeführerin) und die Y._ mit Sitz in Taipei City, Taiwan, (Beschwerdegegnerin) schlossen am 12. Februar 1997 einen Beratungsvertrag im Hinblick auf den Abschluss einer Vereinbarung zwischen der Beschwerdeführerin und der Z._ Ltd. über den Betrieb und Unterhalt eines Elektrizitätswerks. Die Beschwerdeführerin lehnte es in der Folge ab, die Beschwerdegegnerin für ihre erbrachten Beratungsdienstleistungen zu entschädigen.
B. B.a Am 15. September 2004 leitete die Beschwerdegegnerin ein Schiedsverfahren vor der Zürcher Handelskammer ein mit dem Antrag, die Beschwerdeführerin sei zur Zahlung von 10 % des von der Z._ Ltd. an die Beschwerdeführerin bezahlten Betrages, mindestens jedoch von Fr. 5'400'000.-- zu verurteilen. Die Beschwerdeführerin bestritt die Zuständigkeit des Einzelschiedsrichters und beantragte im Übrigen die Abweisung der Klage. Sie erhob dabei diverse Einwände gegen die Gültigkeit des Beratungsvertrages.
B.b Mit Zwischenentscheid vom 28. Juni 2005 bejahte der Einzelschiedsrichter seine Zuständigkeit. Mit einem weiteren Zwischenentscheid vom 23. Februar 2007 stellte er zudem fest, dass der Beratungsvertrag vom 12. Februar 1997 gültig und wirksam sei.
B.c In der Folge entdeckte die Beschwerdeführerin neue Beweismittel. Sie glaubte, damit beweisen zu können, dass es sich beim Beratungsvertrag um ein Schmiergeldversprechen handle und dieser daher nichtig sei. Am 28. Januar 2008 gelangte die Beschwerdeführerin diesbezüglich mit einem Revisionsgesuch an das Bundesgericht. Mit Urteil 4A_42/2008 vom 14. März 2008 wies das Bundesgericht das Revisionsgesuch ab, soweit es darauf eintrat.
B.d Am 17. Juni 2008 erliess der Einzelschiedsrichter einen Zwischen- und Teilentscheid, in dem er unter anderem entschied, welche Zahlungen der Z._ Ltd. an die Beschwerdeführerin für die Berechnung der prozentmässigen Beteiligung der Beschwerdegegnerin berücksichtigt werden müssen.
B.e Mit Endentscheid ("Final Award") vom 19. Dezember 2008 verurteilte der Einzelschiedsrichter die Beschwerdeführerin schliesslich zur Zahlung von Fr. 14'168'385.30 nebst Zins mit unterschiedlichen Fälligkeiten.
C. Mit Beschwerde in Zivilsachen vom 2. Februar 2009 beantragt die Beschwerdeführerin dem Bundesgericht, es sei der Endentscheid des Schiedsgerichts aufzuheben und die Schiedssache zur Abweisung der Schiedsklage und zur neuen Kostenverlegung, eventuell zur neuen Entscheidung an das Schiedsgericht zurückzuweisen.
Die Beschwerdegegnerin schliesst in ihrer Vernehmlassung auf Nichteintreten auf die Beschwerde, eventualiter auf deren Abweisung. Der Einzelschiedsrichter schliesst sinngemäss auf Abweisung der Beschwerde.

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 redigiert. 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. 2.1 Im Bereich der internationalen Schiedsgerichtsbarkeit ist die Beschwerde in Zivilsachen unter den Voraussetzungen der Art. 190-192 IPRG gegen Schiedsentscheide zulässig (<ref-law>). Der Sitz des Schiedsgerichts befindet sich vorliegend in Zürich. Die Beschwerdegegnerin hatte beim Abschluss der Schiedsvereinbarung ihren Sitz in Taiwan, mithin nicht in 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 Der Einzelschiedsrichter hat einen Endentscheid gefällt, der vor Bundesgericht aus allen in <ref-law> genannten Gründen angefochten werden kann. Die Beschwerdeführerin ist durch den angefochtenen Entscheid direkt berührt. Sie hat damit ein rechtlich geschütztes Interesse an dessen Aufhebung (<ref-law>). Die Beschwerde ist form- und fristgerecht (<ref-law>; <ref-law> i.V.m. <ref-law>) eingegangen, weshalb darauf einzutreten ist.
2.3 Die Beschwerde in Zivilsachen gegen internationale Schiedsentscheide (<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 die Beschwerdeführerin mehr verlangt, kann darauf nicht eingetreten werden.
3. Die Beschwerdeführerin rügt einen Verstoss gegen den materiellrechtlichen Ordre public (<ref-law>). Ihrer Ansicht nach stellt der Beratungsvertrag mit der Beschwerdegegnerin ein widerrechtliches bzw. sittenwidriges Schmiergeldversprechen dar. Der angefochtene Schiedsentscheid, der von der Gültigkeit dieses Beratungsvertrags ausgeht, sei folglich mit dem Ordre public unvereinbar. Zur Begründung ihrer Ansicht stützt sich die Beschwerdeführerin auf Beweismittel, die sie im Schiedsverfahren nicht rechtzeitig vorgebracht hat. Wie sie selbst zutreffend festhält, hat das Bundesgericht mit Urteil 4A_42/2009 vom 14. März 2008 entschieden, dass diese Beweismittel im schiedsgerichtlichen Verfahren aufgrund der verspäteten Eingabe zu Recht unberücksichtigt blieben. Die Beschwerdeführerin rügt denn auch nicht mehr, dass das Schiedsgericht die Beweismittel zu Unrecht nicht berücksichtigt habe; sie ist jedoch der Auffassung, dass sie die neuen Beweismittel im bundesgerichtlichen Verfahren gestützt auf <ref-law> vorbringen dürfe.
3.1 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 77 i.V.m. 105 Abs. 1 BGG). Im Bereich der internationalen Schiedsgerichtsbarkeit kann es die Sachverhaltsfeststellungen des Schiedsgerichts weder auf Rüge hin überprüfen (Art. 77 Abs. 2 i.V.m. <ref-law>) noch von Amtes wegen berichtigen oder ergänzen (Art. 77 Abs. 2 i.V.m. <ref-law>). 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. 5 S. 141; <ref-ruling> E. 5.2.2 S. 733; 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 Aktenhinweisen darzulegen, dass entsprechende Sachbehauptungen bereits im Verfahren vor dem Schiedsgericht prozesskonform aufgestellt worden sind (vgl. <ref-ruling> E. 2a S. 486; <ref-ruling> E. 1c S. 473; je mit Hinweisen). Noven können gestützt auf <ref-law> zudem einzig insoweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt.
3.2 Die Gültigkeit des Beratungsvertrags war bereits vor dem Schiedsgericht umstritten, weshalb nicht erst der angefochtene Entscheid Anlass zu den neuen Vorbringen geben kann. Die Beschwerdeführerin ist jedoch der Auffassung, dass gemäss einer neueren Lehrmeinung die behauptete Nichtigkeit eines Rechtsverhältnisses auch noch im bundesgerichtlichen Verfahren von Amtes wegen zu prüfen sei. Dabei seien auch neue Tatsachen zu berücksichtigen. Die Beschwerdeführerin verkennt freilich, dass die einzige Textstelle, auf die sie sich beruft (MEYER, in: Basler Kommentar, Bundesgerichtsgesetz, N. 32 zu <ref-law>), sich lediglich auf die Nichtigkeit öffentlichrechtlicher Verfügungen bezieht. Inwieweit diese Auffassung zutreffend ist, braucht hier nicht entschieden zu werden, da jedenfalls bezüglich der Frage der Nichtigkeit privatrechtlicher Verträge kein Anlass besteht, vom Wortlaut des <ref-law> abzuweichen. Die neuen Beweismittel sind damit unzulässig. Da die für das Bundesgericht verbindlichen tatsächlichen Feststellungen des Schiedsgerichts keine Hinweise enthalten, die auf ein Schmiergeldversprechen schliessen liessen, erweist sich die Beschwerde des Verstosses gegen den materiellrechtlichen Ordre public als unbegründet.
4. Die Beschwerdeführerin rügt weiter, das Schiedsgericht habe den Grundsatz des rechtlichen Gehörs (<ref-law>) verletzt, indem es diverse von ihr prozesskonform vorgebrachte Beweismittel im Zwischen- und Teilentscheid vom 17. Juni 2008 nicht berücksichtigt habe. Dem halten sowohl die Beschwerdegegnerin wie auch der Einzelschiedsrichter entgegen, dass die Beschwerdeführerin die Gehörsrüge verwirkt habe, indem sie nicht sofort vor dem Schiedsgericht eine Verletzung des rechtlichen Gehörs gerügt habe.
4.1 Die Partei, die sich durch eine Verweigerung des rechtlichen Gehörs oder einen anderen Verfahrensmangel für benachteiligt hält, verwirkt ihre Rügen, wenn sie diese nicht rechtzeitig im Schiedsverfahren vorbringt und nicht alle zumutbaren Anstrengungen unternimmt, um sich Gleichbehandlung und rechtliches Gehör zu verschaffen (<ref-ruling> E. 1a S. 388). Es widerspricht Treu und Glauben, einen Verfahrensmangel erst im Rahmen eines Rechtsmittelverfahrens zu rügen, obgleich im Schiedsverfahren die Möglichkeit bestanden hätte, dem Schiedsgericht die Gelegenheit zur Behebung dieses Mangels zu geben (<ref-ruling> E. 1a S. 388; Urteil 4P.72/2001 vom 10. September 2001 E. 4c; JERMINI, Die Anfechtung der Schiedssprüche im internationalen Privatrecht, Diss. Zürich 1997, S. 221 f.; SCHNEIDER, Basler Kommentar, N. 70 ff. zu <ref-law>). Treuwidrig und rechtsmissbräuchlich handelt insbesondere die Partei, welche Rügegründe gleichsam in Reserve hält, um diese bei ungünstigem Prozessverlauf und voraussehbarem Prozessverlust nachzuschieben (vgl. <ref-ruling> E. 3c S. 254).
4.2 Weder aus den tatsächlichen Feststellungen des Schiedsgerichts noch aus der Beschwerdeschrift geht hervor, dass die Beschwerdeführerin gegen die Nichtzulassung der Beweismittel protestiert hätte. Sie kann nur auf schriftliche Rügen in zwei Schreiben vom 14. Juli 2008 und vom 17. Oktober 2008 verweisen, die aber erst nach dem Zwischen- und Teilentscheid vom 17. Juni 2008 vorgebracht wurden. Die Beschwerdeführerin hatte vor Ausfällung des Entscheids vom 17. Juni 2008 mehrmals Gelegenheit, ihre Rüge der Verletzung des rechtlichen Gehörs vorzubringen. Indem sie dies unterlassen und sich erst nach erfolgtem Entscheid darauf berufen hat, hat sie diese Rüge verwirkt.
5. Aus diesen Gründen ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens 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. 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 der Zürcher Handelskammer schriftlich mitgeteilt.
Lausanne, 8. April 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Hurni