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.
Erwägungen:
1.
Nach Art. 54 Abs. 1 BGG 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 abgefasst. 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.
Im Bereich der internationalen Schiedsgerichtsbarkeit ist die Beschwerde in Zivilsachen unter den Voraussetzungen der Art. 190-192 IPRG (SR 291) zulässig (Art. 77 Abs. 1 lit. a BGG).
2.1. Der Sitz des Schiedsgerichts befindet sich vorliegend in Lausanne. Beide Parteien hatten im massgebenden Zeitpunkt ihren Wohnsitz bzw. Sitz ausserhalb der Schweiz (Art. 176 Abs. 1 IPRG). Da die Parteien die Geltung des 12. Kapitels des IPRG nicht ausdrücklich ausgeschlossen haben, gelangen die Bestimmungen dieses Kapitels zur Anwendung (Art. 176 Abs. 2 IPRG).
2.2. Beim angefochtenen Schiedsentscheid handelt es sich um einen Zwischenentscheid (BGE 140 III 520 E. 2.2). Dieser kann nach Art. 190 Abs. 3 IPRG mit Beschwerde in Zivilsachen angefochten werden (BGE 130 III 76 E. 3.1.3, E. 3.2.1 S. 80).
2.3. Die Beschwerde in Zivilsachen im Sinne von Art. 77 Abs. 1 BGG ist grundsätzlich rein kassatorischer Natur, d.h. sie kann nur zur Aufhebung des angefochtenen Entscheids führen (vgl. Art. 77 Abs. 2 BGG, der die Anwendbarkeit von Art. 107 Abs. 2 BGG ausschliesst, soweit dieser dem Bundesgericht erlaubt, in der Sache selbst zu entscheiden). Soweit der Streit die Zuständigkeit des Schiedsgerichts oder dessen Zusammensetzung betrifft, gilt davon eine dahingehende Ausnahme, dass das Bundesgericht selber die Zuständigkeit oder die Unzuständigkeit des Schiedsgerichts feststellen bzw. über die Ablehnung des betreffenden Schiedsrichters befinden kann (BGE 136 III 605 E. 3.3.4 S. 616 mit Hinweisen).
Die Anträge des Beschwerdeführers sind demnach zulässig.
2.4. Die Beschwerde ist innert der Beschwerdefrist vollständig begründet einzureichen (Art. 42 Abs. 1 BGG). 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. BGE 132 I 42 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. BGE 135 I 19 E. 2.2).
Soweit der Beschwerdeführer in seiner Replik darüber hinausgeht, können seine Ausführungen nicht berücksichtigt werden.
2.5. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den das Schiedsgericht festgestellt hat (Art. 105 Abs. 1 BGG). Dazu gehören sowohl die Feststellungen über den Lebenssachverhalt, der dem Streitgegenstand zugrunde liegt, als auch jene über den Ablauf des vorinstanzlichen Verfahrens, also die Feststellungen über den Prozesssachverhalt, zu dem namentlich die Anträge der Parteien, ihre Tatsachenbehauptungen, rechtlichen Erörterungen, Prozesserklärungen und Beweisvorbringen, der Inhalt einer Zeugenaussage, einer Expertise oder die Feststellungen anlässlich eines Augenscheins gehören (BGE 140 III 16 E. 1.3.1 mit Hinweisen).
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 Art. 95 BGG beruht (vgl. Art. 77 Abs. 2 BGG, der die Anwendbarkeit von Art. 97 BGG sowie Art. 105 Abs. 2 BGG 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 Art. 190 Abs. 2 IPRG vorgebracht oder ausnahmsweise Noven berücksichtigt werden (BGE 138 III 29 E. 2.2.1 S. 34; 134 III 565 E. 3.1 S. 567; 133 III 139 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. BGE 115 II 484 E. 2a S. 486; 111 II 471 E. 1c S. 473; je mit Hinweisen; vgl. auch BGE 140 III 86 E. 2 S. 90).
2.6. Der Beschwerdeführer verkennt diese Grundsätze über weite Strecken. Er schildert die Hintergründe der erfolgten Vertragsschlüsse aus eigener Sicht und geht mit seinen Ausführungen verschiedentlich über die verbindlichen Sachverhaltsfeststellungen des Schiedsgerichts hinaus, ohne substanziiert Ausnahmen von der Sachverhaltsbindung geltend zu machen. So stellt er unter Hinweis auf verschiedenste Beweismittel Behauptungen darüber auf, von wem die Verträge entworfen, verhandelt und übersetzt worden seien oder welcher der Unterzeichnenden diese aus sprachlichen Gründen nicht richtig verstanden habe. Diese Vorbringen haben ebenso unbeachtet zu bleiben wie seine Ausführungen zu den Zeichnungsberechtigungen der beteiligten Personen, der Berechnung des "Gesamtwerts" des Beschwerdegegners und den konkreten Genehmigungsbedingungen verschiedener Transaktionen, den tatsächlich zwischen den Beteiligten ausgerichteten Zahlungen, den Hintergründen der erfolgten Vertragskündigung, den Betreibungen und den Konkurseingaben des Beschwerdegegners im Konkursverfahren betreffend die C._ GmbH. Unbeachtlich sind ausserdem die Behauptungen des Beschwerdeführers zum angeblichen tatsächlichen Willen der Parteien, die sich nicht auf die Sachverhaltsfeststellungen im angefochtenen Entscheid stützten lassen.
3.
Der Beschwerdeführer rügt, das TAS habe die Bestimmungen über die Zuständigkeit verletzt (Art. 190 Abs. 2 lit. b IPRG).
3.1. Das Bundesgericht prüft die Zuständigkeitsrüge nach Art. 190 Abs. 2 lit. b IPRG in rechtlicher Hinsicht frei, einschliesslich materieller Vorfragen, von deren Beantwortung die Zuständigkeit abhängt. Demgegenüber überprüft es die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids auch im Rahmen der Zuständigkeitsrüge nur, wenn gegenüber diesen Sachverhaltsfeststellungen zulässige Rügen im Sinne von Art. 190 Abs. 2 IPRG vorgebracht oder ausnahmsweise Noven (Art. 99 BGG) berücksichtigt werden (BGE 142 III 220 E. 3.1, 239 E. 3.1; 140 III 477 E. 3.1 S. 477, 520 E. 3.1; 138 III 29 E. 2.2.1; je mit Hinweisen).
Unter einer Schiedsvereinbarung ist eine Übereinkunft zu verstehen, mit der sich zwei oder mehrere bestimmte oder bestimmbare Parteien einigen, eine oder mehrere, bestehende oder künftige Streitigkeiten verbindlich unter Ausschluss der ursprünglichen staatlichen Gerichtsbarkeit einem Schiedsgericht nach Massgabe einer unmittelbar oder mittelbar bestimmten rechtlichen Ordnung zu unterstellen (BGE 140 III 134 E. 3.1 S. 138; 130 III 66 E. 3.1 S. 70). Entscheidend ist, dass der Wille der Parteien zum Ausdruck kommt, über bestimmte Streitigkeiten ein Schiedsgericht, d.h. ein nichtstaatliches Gericht, entscheiden zu lassen (BGE 140 III 134 E. 3.1 S. 138; 138 III 29 E. 2.2.3 S. 35; 129 III 675 E. 2.3 S. 679 f.).
3.2. Der Beschwerdeführer bestreitet nicht, dass sich die Parteien gültig verpflichtet haben, allfällige Streitigkeiten aus dem First Private Employment Contract und dem Second Private Employment Contract durch ein Schiedsgericht entscheiden zu lassen. Er stellt sich jedoch auf den Standpunkt, die Kammer zur Beilegung von Streitigkeiten der FIFA sei nicht zuständig, sondern einzig und unmittelbar das Tribunal Arbitral du Sport. Seine Rüge geht demnach dahin, das TAS habe als einzige Instanz zu entscheiden und nicht als Berufungsinstanz nach Durchführung eines verbandsinternen Verfahrens vor der Kammer zur Beilegung von Streitigkeiten der FIFA (zur Zuständigkeit des TAS als ordentliche oder als Berufungsinstanz etwa Urteil 4A_392/2008 vom 22. Dezember 2008).
3.3.
3.3.1. Der Beschwerdeführer stellt zu Recht nicht grundsätzlich in Frage, dass die Parteien an die verbandsrechtlichen Bestimmungen der FIFA gebunden sind. Sein Einwand, es handle sich im konkreten Fall um eine Auseinandersetzung zwischen dem Beschwerdegegner und der C._ GmbH, auf welche das einschlägige FIFA-Reglement von vornherein keine Anwendung finde, da er selber nicht gültig Partei des First und des Second Private Employment Contracts geworden sei, ist nicht stichhaltig. Am vorliegenden Verfahren sind einzig der Beschwerdeführer und der Beschwerdegegner beteiligt. Wer aus dem First bzw. dem Second Private Employment Contract gegenüber wem wieviel schuldet, ist eine materielle Frage, die von der zuständigen Instanz zu prüfen sein wird, und nicht eine solche der Zuständigkeit. Entsprechendes gilt für das Vorbringen, eine sich aus dem Second Private Employment Contract ergebende Verpflichtung zur Zahlung eines Geldbetrags in Euro verstosse gegen zwingendes Recht und sei daher nicht rechtswirksam.
Ausserdem ist seine Argumentation widersprüchlich, zumal sich der Beschwerdeführer selber auf die mit dem First und dem Second Private Employment Contract vereinbarte Schiedsklausel stützt und daraus ableiten will, diese schliesse aus, dass vorgängig zum Entscheid des TAS zunächst die Kammer zur Beilegung von Streitigkeiten der FIFA über die Streitsache befinde.
3.3.2. Das Schiedsgericht hat massgebend auf Artikel 22 ("Zuständigkeit der FIFA") des FIFA-Reglements bezüglich Status und Transfer von Spielern ("Regulations for the Status and Transfer of Players"; Ausgabe 2009) abgestellt, der wie folgt lautet:
"Without prejudice to the right of any player or club to seek redress before a civil court for employment-related disputes, FIFA is competent to hear:
-..]
b) employment-related disputes between a club and a player of an international dimension, unless an independent arbitration tribunal guaranteeing fair proceedings and respecting the principle of equal representation of players and clubs has been established at national level within the framework of the association and/or a collective bargaining agreement; [...]"
("Unbeschadet des Rechts jedes Spielers oder Vereins, bei arbeitsrechtlichen Streitigkeiten ein Zivilgericht anzurufen, ist die FIFA in folgenden Fällen zuständig:
-..]
b) internationale arbeitsrechtliche Streitigkeiten zwischen einem Verein und einem Spieler, falls auf nationaler Ebene innerhalb des Verbandes und/oder im Rahmen eines Tarifvertrags kein unabhängiges Schiedsgericht angerufen werden kann, das ein faires Verfahren garantiert und auf einer paritätischen Vertretung von Spielern und Vereinen basiert; [...]")
Das Schiedsgericht erwog, dass es sich beim konkreten Rechtsstreit um eine internationale arbeitsrechtliche Streitigkeit im Sinne von Artikel 22 (b) des FIFA-Reglements bezüglich Status und Transfer von Spielern handle. Dies leuchtet auch ohne Weiteres ein: Der Beschwerdegegner hat als professioneller Fussballspieler für den Beschwerdeführer in X._ gearbeitet und macht ausstehende Lohnansprüche sowie vertraglichen Schadenersatz aus dem Arbeitsverhältnis geltend.
Internationale arbeitsrechtliche Streitigkeiten zwischen einem Verein und einem Spieler sind nach Artikel 22 (b) in Verbindung mit Artikel 24 Abs. 1 des Reglements grundsätzlich der Kammer zur Beilegung von Streitigkeiten der FIFA zu unterbreiten. Gegen Entscheidungen der Kammer kann nach Art. 24 Abs. 3 a.E. beim TAS Berufung eingelegt werden. Abgesehen vom Recht, ein Zivilgericht anzurufen, das von der Regelung unberührt bleibt, sieht Artikel 22 (b) als Ausnahme von der Zuständigkeit der FIFA lediglich den Fall vor, dass auf nationaler Ebene innerhalb des Verbands und/oder im Rahmen eines Tarifvertrags ("collective bargaining agreement") ein unabhängiges Schiedsgericht angerufen werden kann, das ein faires Verfahren garantiert und auf einer paritätischen Vertretung von Spielern und Vereinen ("equal representation of players and clubs") basiert. Der Beschwerdeführer bringt nicht etwa vor, es habe auf nationaler Ebene ein paritätisch zusammengesetztes Schiedsgericht bestanden, das diesen Vorgaben genügen würde. Wie im angefochtenen Entscheid zutreffend ausgeführt, stellt auch das TAS kein derartiges nationales Schiedsgericht dar, weshalb es zu Recht davon ausging, dass im konkreten Fall keine in Artikel 22 vorgesehene Ausnahme von der Zuständigkeit der FIFA-Kammer vorlag. Die in der Beschwerde vertretene Auffassung, das FIFA-Reglement bezüglich Status und Transfer von Spielern schränke das Recht der daran gebundenen Parteien nicht ein, selbst ein Schiedsgericht zu bestimmen, überzeugt angesichts der in Artikel 22 klar umschriebenen Ausnahmen nicht. Inwiefern das in dieser Bestimmung vorbehaltene Recht, ein Zivilgericht anzurufen, "in Übereinstimmung mit Art. 30 BV" auch die Möglichkeit einschliessen soll, anstelle eines staatlichen Gerichts ein Schiedsgericht zu wählen, wird vom Beschwerdeführer nicht hinreichend dargetan und vermag auch nicht einzuleuchten, wurde der Vorbehalt nach der in der Beschwerdeschrift zitierten Kommentarstelle doch im Hinblick auf die in verschiedenen Rechtsordnungen zu beachtende zwingende Zuständigkeit staatlicher Gerichte angebracht, die eine Vereinbarung eines Schiedsgerichts gerade ausschliesst.
3.3.3. Vor diesem Hintergrund verfängt der Einwand des Beschwerdeführers nicht, die Parteien hätten die Zuständigkeit der Kammer zur Beilegung von Streitigkeiten der FIFA zugunsten des TAS mit der Schiedsklausel im First Private Employment Contract ausgeschlossen, die auch für dessen Ergänzung durch den Second Private Employment Contract gilt. Dabei ist zu berücksichtigen, dass es sich bei verbandsinternen Entscheidungsorganen nicht um Schiedsgerichte handelt und deren Entscheidungen lediglich einfache Willensäusserungen der beteiligten Vereine - und nicht etwa Rechtsprechungsakte - darstellen (BGE 119 II 271 E. 3 S. 275 f.; Urteile 4A_222/2015 vom 28. Januar 2016 E. 3.2.3.1; 4A_374/2014 vom 26. Februar 2015 E. 4.3.2.1). Dies gilt auch für die erwähnte FIFA-Kammer (vgl. BGE 136 III 345 E. 2.2.1 S. 349), wie im Übrigen auch der Beschwerdeführer anerkennt. Dies spricht auch im Rahmen der Auslegung der im First Private Employment Contract enthaltenen Schiedsklausel für das Verständnis, wonach die Parteien mit der gewählten Formulierung die Zuständigkeit anderer rechtsprechender Instanzen neben dem TAS - und nicht etwa allfällige verbandsinterne Verfahren - ausschliessen wollten.
Die isolierte Auslegung nach dem Wortlaut der Schiedsklausel, wie sie in der Beschwerde vertreten wird, greift auch aus anderen Gründen zu kurz: Das Schiedsgericht berücksichtigte zutreffend die weiteren Umstände des Vertragsschlusses, so insbesondere, dass im First Private Employment Contract drei Vertragsparteien aufgeführt sind und diese beabsichtigten, auch C._ GmbH, auf welche die massgebenden FIFA-Reglemente - so insbesondere Artikel 22 (b) des FIFA-Reglements bezüglich Status und Transfer von Spielern - unbestrittenermassen nicht anwendbar sind, der Schiedsgerichtsbarkeit des TAS zu unterstellen. Unter Berücksichtigung des ebenfalls am 28. August 2008 abgeschlossenen First Standard Employment Contracts zwischen dem Beschwerdeführer und dem Beschwerdegegner, in dessen Schiedsklausel die Zuständigkeit der Organe der FIFA ausdrücklich erwähnt wird, konnte das Schiedsgericht daher rechtsfehlerfrei schliessen, dass die Schiedsklausel im First Private Employment Contract nach Treu und Glauben dahingehend zu verstehen ist, dass damit für arbeitsrechtliche Streitigkeiten zwischen dem Beschwerdeführer und dem Beschwerdegegner die verbandsinternen Verfahren vor einem Schiedsentscheid des TAS nicht ausgeschlossen werden sollten.
Das TAS ging demnach zu Recht davon aus, dass es nicht unmittelbar über den Rechtsstreit zwischen den Parteien zu entscheiden habe, sondern als Berufungsinstanz nach Durchführung eines verbandsinternen Verfahrens vor der FIFA-Kammer zur Beilegung von Streitigkeiten. Der angefochtene Entscheid ist unter dem Blickwinkel von Art. 190 Abs. 2 lit. b IPRG nicht zu beanstanden.
4.
Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 sowie 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 dem Beschwerdeführer auferlegt.
3.
Der Beschwerdeführer hat den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 50'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien, der Fédération Internationale de Football Association (FIFA) und dem Tribunal Arbitral du Sport (TAS) schriftlich mitgeteilt.
Lausanne, 7. Februar 2017
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Leemann