Sachverhalt: A. A.a A._ (Kläger, Beschwerdeführer) ist bulgarischer Staatsbürger und wohnt in Sofia. Er war Cheftrainer der nationalen Fussballmannschaft Bulgariens. Die Bulgarische Fussballunion (BFU, Beklagte, Beschwerdegegnerin) ist der nationale Fussballverband Bulgariens. Sie gehört der Fédération Internationale de Football Association (FIFA) an. A.b Am 11. Januar 2008 schlossen die Parteien einen Arbeitsvertrag ab, mit dem der Kläger für eine feste Zeitdauer bis zum 31. Dezember 2009 als Cheftrainer der bulgarischen Nationalmannschaft eingestellt wurde gegen einen Monatslohn von EUR 11'000.--, zuzüglich erfolgsabhängige Boni und Spesen. Ziffer 16 des Arbeitsvertrags lautet wie folgt: "The disputes concerning the interpretation of the meaning and the performance of the contract will be resolved amicably by agreement of the parties. In case an agreement is impossible to reach, the dispute shall be referred for resolving by the competent court. The parties to the contract recognize the Court of Arbitration for Sport (CAS) in Lausanne, Switzerland as in this case the Statute and the regulations of BFU and the provisions of Bulgarian legislation will apply." Am 13. Januar 2009 kündigte die Beklagte das Arbeitsverhältnis vorzeitig und zahlte dem Kläger einen Monatslohn aus. A.c Am 19. Januar 2009 leitete der Kläger beim Regionalgericht Sofia ein Zivilverfahren ein und beantragte, die Beklagte sei zur Zahlung von EUR 132'000.-- zu verurteilen. Das Regionalgericht erklärte sich mit der Begründung für zuständig, arbeitsrechtliche Streitigkeiten seien nach Art. 19 Abs. 1 der bulgarischen Zivilprozessordnung (bZPO) nicht schiedsfähig, sondern müssten von den staatlichen Gerichten beurteilt werden. Das Gericht wies die Klage jedoch ab, indem es erwog, die vom Kläger angerufene Vertragsbestimmung, nach der bei einseitiger Vertragsauflösung eine Konventionalstrafe geschuldet ist, widerspreche dem bulgarischen Arbeitsrecht und sei nichtig. Art. 19 Abs. 1 bZPO sieht (in seiner englischen Übersetzung) Folgendes vor: "The parties to a property dispute may agree that it be settled by a court of arbitration, unless the dispute has as its subject property rights or possession of immoveable property, alimony or rights as per employment relationship." A.d Am 13. Oktober 2011 reichte der Kläger beim Regionalgericht Sofia eine weitere Klage ein und verlangte eine Entschädigung von sechs Monatslöhnen wegen Vertragsverletzung. Das Regionalgericht erklärte sich mangels Schiedsfähigkeit der Streitsache wiederum in Anwendung von Art. 19 bZPO für zuständig. Das Regionalgericht vertagte das Verfahren und lud die Parteien auf den 8. Mai 2012 zu einer Verhandlung. B. Am 8. November 2011 erhob der Kläger beim Tribunal Arbitral du Sport (TAS) Schiedsklage gegen die Beklagte und stellte im Verfahrensverlauf die folgenden Rechtsbegehren: "a. Declare that the CAS has jurisdiction over the dispute and the Parties to this arbitration. b. Declare that the Employment Contract dated 11 January 2008 entered into by and between the Bulgarian Football Union (the Respondent) and Mr. A._ (the Claimant) was terminated without just cause; c. Order BFU to pay to the Claimant as compensation for the termination of the Employment Contract 11 salaries in the amount of EUR 121,000 corresponding to the remaining value of the Employment Contract; d. Order BFU to pay to the Claimant simple interest at 5 % per annum on the amount of EUR 121,000 from 15 January 2009 until full and final payment; e. Order BFU to pay to the Claimant further allowances and payments listed in para. 20 of the RFA [Request for Arbitration] above the amount of which is to be further specified; f. Order BFU to pay to the Claimant simple interest at 5 % per annum on the amounts related to further allowances and payments listed in para. 20 of the RFA from issuance of the award until full and final payment; g. Order BFU to pay all the costs of the arbitration, including without limitation the fees and expenses of the Panel and the CAS; h. Order BFU to pay to the Claimant its legal fees and expenses; i. Award such other relief as the Panel deems appropriate." Die Beklagte erhob die Einrede der Unzuständigkeit: Der Rechtsstreit sei nicht schiedsfähig und zwingend von den staatlichen Gerichten in Bulgarien zu beurteilen, die Schiedsvereinbarung sei ungültig und der Kläger habe auf die Anrufung der Schiedsklausel verzichtet. Im Weiteren stehe der erhobenen Schiedsklage die Rechtskraftwirkung bereits ergangener Gerichtsurteile (res iudicata) entgegen. Mit Schiedsentscheid vom 24. Mai 2012 erklärte sich das TAS mangels Schiedsfähigkeit für unzuständig. Es erachtete Art. 19 Abs. 1 bZPO für anwendbar, der arbeitsrechtliche Streitigkeiten von der Beurteilung durch ein Schiedsgericht ausschliesst. Diesem Ergebnis stehe auch Art. 177 IPRG nicht im Weg, zumal das IPRG eine Berücksichtigung zwingender Bestimmungen eines ausländischen Rechts zulasse. Im Weiteren wies das TAS darauf hin, es bestehe die reelle Gefahr, dass ein Schiedsentscheid des TAS in Bulgarien nicht durchgesetzt werden könne. C. Mit Beschwerde in Zivilsachen beantragt der Kläger dem Bundesgericht, der Schiedsentscheid vom 24. Mai 2012 sei aufzuheben und das TAS sei für zuständig zu erklären. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde. Das TAS hat auf eine Vernehmlassung verzichtet. Der Beschwerdeführer hat dem Bundesgericht am 28. November 2012 eine Replik, die Beschwerdegegnerin am 20. Dezember 2012 eine Duplik eingereicht. 