Sachverhalt: A. A.a. Der FC A._ (Beklagter, Beschwerdeführer) ist ein Fussballclub mit Sitz in X._. Er ist Mitglied des Fussballverbands von X._, der seinerseits der Fédération Internationale de Football Association (FIFA, Verfahrensbeteiligte) angehört, einem Verein schweizerischen Rechts mit Sitz in Zürich. B._ (Kläger, Beschwerdegegner) ist ein Fussballspieler mit Wohnsitz in Y._. A.b. Am 28. August 2008 schloss B._ mit dem FC A._ einen Arbeitsvertrag ("First Standard Employment Contract") ab. Dieser wurde bei der Professional Football League of X._ registriert und enthält keine konkreten Angaben zum vereinbarten Lohn. Der Vertrag sieht unter anderem Folgendes vor: "7.1 All disputes and disagreements which may arise during performance of obligations under the present contract, coordinate the parties by negotiations. The parties are obliged to abstain from the decision of disputes among themselves in courts of the general jurisdiction, for this purpose it is necessary to use the appropriate bodies of Professional football league of X._, X._ Football Federation, AFC FIFA and the Court of Arbitration for Sport". Ebenfalls am 28. August 2008 unterzeichnete B._ eine Vereinbarung ("First Private Employment Contract") mit dem FC A._ und der C._ GmbH, einer Gesellschaft mit Sitz in Zug. Diese enthält unter anderem die folgenden Bestimmungen: "2. REMUNERATION AND ENTITLEMENTS 2.1 For the Period of 28, August, 2008 until the end of the season 2009, and in consideration of the Athlete observing and performing the covenants and obligations of this Contract, the Company shall pay the Athlete a basic salary of EUR 6.500.000,00 (six million five hundred thousand Euros), plus EUR 1.000.000,00 (one million Euros) regarding the transferring compensation of the athlete, to be paid as follows: a) EUR 3.500.000,00 (three million five hundred thousand Euros) free taxes to be paid on the signing date of the Contract, in a bank account to be indicated in writing by the Athlete, plus: b) EUR 2.000.000,00 (two million Euros) free taxes, to be paid on September 25th, 2008. c) EUR 2.000.000,00 (two million Euros) free taxes, to be paid on October 25th, 2008. [...] 5. JURISDICTION AND CHOICE OF LAW 5.1 Any dispute arising from or related to the present contract will be submitted exclusively to an arbitration procedure before the Court of Arbitration for Sport (CAS-TAS) in Lausanne, Switzerland, and resolved definitely in accordance with the Code of sports-related arbitration." Am 17. November 2008 schlossen B._, der FC A._ und die C._ GmbH eine weitere Vereinbarung ab, die als "TERM OF EMPLOYMENT CONTRACT EXTENSION" bezeichnet wurde (nachfolgend: "Second Private Employment Contract"). Diese sieht unter anderem Folgendes vor: "2. For the contractual however extending period the parts establish the values and dates of payment below mentioned, remaining for the season of 2009 the waked up values and dates already in clause 2 and 2.1 of the originary Employment contract: a) For the season of 2010 the Employer will pay Contracted to the importance net (liquid) of six Million Euros (6.000.000,00), divided in two (2) equal parcels of tree Million Euros (3.000.000,00), being the first one in day 25 of august of 2010 and the second one in 25 of September of 2009. b) For the season of 2011 the Employer will pay Contracted to the importance net (liquid) of six Million Euros (6.000.000,00), divided in two (2) equal parcels of tree Million Euros (3.000.000,00), being the first one in day 25 of august 2010 and the second one in 25 of September 2010. 3. To be continue being valid for the contractual however extending period, all the rest clauses of the Employment contract firmed between Employer and Contracted in 28 of August 2008 and that they had not damaged no modification with the present instrument from Extension." Am 1. April 2009 schlossen B._, der FC A._ und die C._ GmbH eine als "SERVICE CONTRACT" bezeichnete Vereinbarung ab, nach der B._ als Berater des Fussballclubs FC A._ tätig werden solle. Am 20. Januar 2010 schlossen B._ und der FC A._ einen weiteren Vertrag ("Second Standard Employment Contract") ab, den sie wiederum bei der Professional Football League of X._ registrieren liessen. Die Vertragsbedingungen sind vergleichbar mit denjenigen des First Standard Employment Contract, ausser dass das Tribunal Arbitral du Sport (TAS) in Ziffer 7.1 des Second Standard Employment Contract unerwähnt bleibt. A.c. Mit Schreiben vom 26. Juli 2010 forderte B._ den FC A._ und die C._ GmbH auf, den Betrag von EUR 6 Mio. in Erfüllung des Second Private Employment Contract innerhalb von 10 Tagen zu bezahlen, ansonsten er den Vertrag auflösen werde. Am 1. August 2010 spielte B._ zum letzten Mal für den FC A._. Mit Schreiben vom 9. August 2010 erklärte der Spieler, aufgrund der ausgebliebenen Zahlung erachte er sich vertraglich nicht mehr gebunden. B. B.a. Am 19. August 2010 beantragte B._ der Kammer zur Beilegung von Streitigkeiten (Dispute Resolution Chamber) der FIFA, der FC A._ sei zur Zahlung von EUR 15'919'013.-- (EUR 8'269'013.-- ausstehende Lohnansprüche und EUR 7'650'000.-- Schadenersatz) zu verpflichten und es seien Sanktionen gegen diesen zu verhängen. Der FC A._ äusserte sich nicht zum Begehren. Mit Entscheid vom 6. November 2014 hiess die Kammer zur Beilegung von Streitigkeiten der FIFA das Begehren teilweise gut und verpflichtete den Beklagten zur Begleichung ausstehender Lohnansprüche im Betrag von EUR 6 Mio. sowie zur Zahlung von EUR 5'664'000.-- Schadenersatz, jeweils zuzüglich Zins. B.b. Der FC A._ focht den Entscheid der Kammer zur Beilegung von Streitigkeiten der FIFA vom 6. November 2014 beim Tribunal Arbitral du Sport mit Berufung an und beantragte, der Entscheid sei für nichtig zu erklären, eventualiter aufzuheben; subeventualiter sei die Streitsache an die Kammer zur Beilegung von Streitigkeiten zurückzuweisen, um das Verfahren unter vollständiger Wahrung seiner Parteirechte neu durchzuführen. Dabei brachte er insbesondere vor, der FIFA-Kammer fehle es an der Zuständigkeit. Am 22. Dezember 2015 fand in Lausanne eine mündliche Verhandlung statt. Mit Schiedsentscheid vom 4. Juli 2016 hiess das TAS die Berufung des Beklagten teilweise gut; es erklärte die Kammer zur Beilegung von Streitigkeiten der FIFA für zuständig, über den Rechtsstreit zu entscheiden, es hob den angefochtenen Entscheid vom 6. November 2014 auf und wies die Sache zu neuer Beurteilung an die FIFA-Kammer zurück. C. Mit Beschwerde in Zivilsachen beantragt der FC A._ dem Bundesgericht, es sei der Schiedsspruch des Tribunal Arbitral du Sport vom 4. Juli 2016 aufzuheben und es sei die Zuständigkeit der Kammer zur Beilegung von Streitigkeiten der FIFA zur Beurteilung der Streitsache zu verneinen. Eventualiter sei der angefochtene Schiedsentscheid vom 4. Juli 2016 aufzuheben und die Sache an das TAS zurückzuweisen zur Neubeurteilung unter Berücksichtigung der Unzuständigkeit der FIFA-Kammer zur Beilegung von Streitigkeiten. Subeventualiter sei der angefochtene Entscheid aufzuheben und die Sache zur Neubeurteilung der Zuständigkeit der FIFA-Kammer an das TAS zurückzuweisen. Der Beschwerdegegner beantragt die Abweisung der Beschwerde. Das TAS hat auf eine Vernehmlassung verzichtet. Die FIFA hat auf eine aktive Beteiligung am Verfahren verzichtet. Der Beschwerdeführer hat dem Bundesgericht eine Replik eingereicht. D. Mit Verfügung vom 14. Oktober 2016 gewährte das Bundesgericht der Beschwerde die aufschiebende Wirkung.