Sachverhalt: A. A.a. X._ SA de C.V., I._/Mexico, (Beklagte, Beschwerdeführerin) ist ein professioneller Fussballclub und als solcher Mitglied des mexikanischen Fussballverbands. A._ (Kläger, Beschwerdegegner) ist ein brasilianischer Fussballspieler mit Wohnsitz in K._/Brasilien. A.b. Am 23. Juli 2007 schlossen die Parteien einen Arbeitsvertrag ab, mit dem sich A._ verpflichtete, während der Spielsaisons 2007/2008, 2008/2009 und 2009/2010 für X._ SA de C.V. zu spielen. Als Entgelt wurde ein jährliches Salär von USD 500'000.--, zahlbar in jeweils zehn Raten von USD 50'000.--, vereinbart. Im Weiteren versprach der Fussballclub dem Spieler eine Transferentschädigung von insgesamt USD 400'000.--, zahlbar in drei Raten (USD 120'000.--, USD 140'000.-- und USD 140'000.--). Zwischen August und Dezember 2008 sowie Dezember 2008 und Mai 2009 wurde A._ nach einer Vereinbarung zwischen den Parteien jeweils an einen brasilianischen Fussballclub ausgeliehen. Nach dem Ende der Saison 2008/2009 - als die letzte Rate der Transferentschädigung im Umfang von USD 140'000.-- noch nicht bezahlt war - teilte X._ SA de C.V. dem Fussballspieler A._ mit, dass sie den Vertrag vorzeitig auflösen wolle. Daher unterzeichneten die Parteien am 30. August 2009 eine Auflösungsvereinbarung ("Agreement of Early Termination of Contract"), die eine einmalige Entschädigung zugunsten des Spielers von MXN 1.3 Mio. vorsah, zahlbar per 17. September 2009. Für den Fall, dass die Auflösungsentschädigung nicht innerhalb von zehn Tagen nach dem 17. September 2009 bezahlt würde, vereinbarten sie die Unwirksamkeit der Auflösungsvereinbarung. Die Zahlung blieb aus. B. B.a. Am 11. März 2010 erhob A._ Klage bei der Dispute Resolution Chamber der Fédération Internationale de Football Association (FIFA). Diese erklärte sich mit Entscheid vom 20. November 2010 für unzuständig. B.b. Am 17. Februar 2011 erhob er Klage bei der Conciliation and Resolution of Controversies Commission (CRCC) des mexikanischen Fussballverbands. Am 26. Juli 2011 entschied die CRCC, sie könne die Klage nicht an die Hand nehmen, weil die Frist zur Geltendmachung der Ansprüche nach mexikanischem Arbeitsrecht und Art. 11 des Reglements der CRCC abgelaufen sei. B.c. Am 16. August 2011 erhob der Kläger beim Tribunal Arbitral du Sport (TAS) Berufung gegen den Entscheid der CRCC vom 26. Juli 2011. Am 10. Februar 2012 teilte das TAS den Parteien mit, dass der Präsident der Berufungskammer Frau Rechtsanwältin Margarita Echeverria Bermudez als Einzelschiedsrichterin ernannt habe. Nach Anhörung der Parteien entschied sich die Einzelschiedsrichterin, auf die Durchführung einer mündlichen Verhandlung zu verzichten. B.d. Mit Schiedsentscheid vom 26. Juni 2012 hiess die Einzelschiedsrichterin die Berufung des Klägers gut (Dispositiv-Ziffer 1), sie hob den Entscheid der CRCC vom 26. Juli 2011 auf (Dispositiv-Ziffer 2) und verurteilte X._ SA de C.V. zur Zahlung von USD 590'000.-- an A._, zuzüglich Zins zu 5 % seit dem 28. September 2009 (Dispositiv-Ziffer 3). Im Weiteren regelte sie die Kosten- und Entschädigungsfolgen (Dispositiv-Ziffern 4 und 5) und wies sämtliche weiteren Anträge ab (Dispositiv-Ziffer 6). C. Mit Beschwerde in Zivilsachen beantragt die Beklagte dem Bundesgericht, es sei der Schiedsentscheid des TAS vom 26. Juni 2012 aufzuheben und es sei festzustellen, dass die Einzelschiedsrichterin vorschriftswidrig ernannt wurde, eventualiter dass die Einzelschiedsrichterin unzuständig war, und es sei folglich festzustellen, dass das Verfahren vor einem Dreierschiedsgericht durchzuführen ist. Eventualiter sei der Schiedsentscheid vom 26. Juni 2012 aufzuheben und die Streitsache zur Feststellung der vorschriftswidrigen Ernennung der Einzelschiedsrichterin, eventualiter zur Feststellung der Unzuständigkeit der Einzelschiedsrichterin sowie zur Einsetzung eines Dreierschiedsgerichts an das TAS, eventualiter an die Einzelschiedsrichterin, zurückzuweisen. Subeventualiter seien die Ziffern 1 - 5 des angefochtenen Schiedsentscheids aufzuheben und die Streitsache zur neuen Entscheidung an das Schiedsgericht zurückzuweisen. Der Beschwerdegegner beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Das TAS beantragt die Abweisung der Beschwerde. Die Beschwerdeführerin hat dem Bundesgericht am 17. April 2013 eine Replik eingereicht. Mit Schreiben vom 6. Mai 2013 verzichtete der Beschwerdegegner auf eine Duplik. D. Mit Verfügung vom 18. Dezember 2012 hat das Bundesgericht das Sicherstellungsbegehren des Beschwerdegegners gutgeheissen und die Beschwerdeführerin aufgefordert, als Sicherstellung einer allfällig dem Beschwerdegegner geschuldeten Parteientschädigung Fr. 9'500.-- in bar zu hinterlegen. Der Betrag ging fristgerecht bei der Bundesgerichtskasse ein. 