Sachverhalt:
A.
A.a. A._ (Kläger, Beschwerdeführer) ist ein französischer Fussballspieler mit Wohnsitz in C._.
B._ FC (Beklagter, Beschwerdegegner) ist ein Fussballclub mit Sitz in D._. Er ist Mitglied des zypriotischen Fussballverbands, der seinerseits der Fédération Internationale de Football Association (FIFA) angehört.
A.b. Am 22. Juni 2011 schlossen die Parteien einen bis 31. Mai 2013 befristeten Arbeitsvertrag ab.
Am 23. Juni 2011 unterzeichneten die Parteien zusätzlich zum erwähnten Arbeitsvertrag eine Vereinbarung mit gleicher Laufzeit, die eine zusätzliche Entschädigung zugunsten des Spielers vorsah.
Der Arbeitsvertrag vom 22. Juni 2011 lautete unter anderem wie folgt:
"a) In consideration of the above the EMPLOYER shall pay the following emoluments and fringe benefits to the EMPLOYEE during the course of this employment:
- For the term of this employment for the season 2011/2012, salary amounting to EURO 30 000 (Thirty Thousand EURO) payable in 10 (ten) instalments of EURO 3 000 (Three Thousand EURO) per month and with a grace period of 90 days, as the first instalment to be paid on the 31st of August, 2011 and the last to be paid on 31st of May 2012.
- For the term of this employment for the season 2012/2013, salary amounting to EURO 40 000 (Forty Thousand EURO) payable in 10 (ten) installments of EURO 4000 ([...] Thousand EURO) per month and with a grace period of 90 days, as the first installment to be paid on the 31st of August, 2012 and the last to be paid on 31st of May 2013.
If the Club undergoes to the second division, this contract is not valid and the Player must terminate his services to the team, having no further demands.
b) Any part of the fees payable to the Cyprus Government for the issue of the employment permit will be paid by the EMPLOYER.
It is understood between the parties that all money paid will be tax free, meaning that the EMPLOYER is responsible to pay all relevant taxes to the various Government Authorities."
Die Vereinbarung vom 23. Juni 2011 sah unter anderem Folgendes vor:
"WHEREAS the parties have already signed a Contract of Employment on the day of the 22nd of June, 2011.
NOW THE PARTIES AGREE THE FOLLOWING IN ADDITION TO THE SAID CONTRACT OF EMPLOYMENT
In exchange of the services the PLAYER will offer to the CLUB, the CLUB has to pay in addition to the said contract:
- For the season 2011/2012 salary amounting of 80 000 EURO (Eighty Thousand EURO) payable in ten (10) installments of 8 000 EURO (Eight Thousand EURO) per month and with a grace period of 90 days, as the first installment to be paid on the 31st of August, 2011 and the last to be paid the 31st of May 2012.
- For the season 2012/2013 salary amounting of 90 000 EURO (Ninety Thousand EURO) payable in ten (10) installments of 9 000 EURO (Nine Thousand EURO) per month and with a grace period of 90 days, as the first installment to be paid on the 31st of August, 2012 and the last to be paid the 31st of May 2013.
- The Player shall receive the amount of 30 000 EURO (Thirty Thousand EURO) as signing fees.
- The Player shall receive also at the end of June, 2012 (30/6/12) the amount of 20 000 EURO (Twenty Thousand EURO) as signing fees for the season 2012/2013.
- The Player shall also receive from the Club the amount of 6 000 EURO (Six Thousand EURO) for accommodation and the amount of 5 000 EURO (Five Thousand EURO) for air tickets.
- The Club will provide to the Player a car."
A._ nahm seine Tätigkeit beim B._ FC im Juli 2011 auf und war ab Beginn der Spielsaison 2011/2012 regelmässig im Einsatz. Im Januar 2012 erlitt er jedoch einen Achillessehnenriss, der ihn davon abhielt, die übrigen Fussballspiele der Saison zu bestreiten.
Obwohl von seiner Verletzung noch nicht geheilt, nahm der Spieler im Juni 2012 das Training für die Spielsaison 2012/2013 wieder auf, aber der B._ FC erlaubte dem Spieler nicht, an der Vorbereitung für die neue Saison teilzunehmen.
Mit Schreiben vom 20. Juni 2012 beklagte sich der Spieler beim Club, dass er medizinisch nicht hinreichend versorgt werde.
Im Juli und September 2012 richtete der Spieler insgesamt vier Schreiben an den Club und verlangte neben der medizinischen Behandlung verschiedene Zahlungen für ausstehende Lohnansprüche, Auslagen für Unterkunft, Auto und Flugtickets für die Monate April, Mai und August 2012 sowie den Einstiegsbonus ("signing-on fee") für die Spielsaison 2012/2013.
Am 28. September 2012 zahlte der B._ FC den Betrag von EUR 28'075.--, wofür A._ eine Empfangsbestätigung ausstellte ("Full settlement of any amount due until 30/9/12. Salary of August and September, airtickets, rents, car etc."). Am gleichen Tag zahlte der Club den Einstiegsbonus ("signing-on fee") von EUR 20'000.-- für die Spielsaison 2012/2013.
Während der Zeitperiode vom 12. Juni 2012 bis 25. Januar 2013 erhielt A._ vom General Manager des B._ FC 16 aufeinanderfolgende Freistellungsbescheinigungen ausgestellt, da er aufgrund seiner Verletzung nicht trainieren konnte.
Mit Schreiben vom 16. Januar 2013 beschwerte sich A._ beim B._ FC erneut darüber, dass er jeweils zu spät bezahlt werde. Er beanstandete unter anderem, dass seine Monatslöhne, seine Mietauslagen sowie seine Flug- und Autokosten für Oktober, November und Dezember 2012 noch nicht beglichen worden seien. Er forderte einen Gesamtbetrag von EUR 45'670.--, setzte dem B._ FC eine achttägige Frist zur Zahlung an und drohte im Fall der Nichtzahlung an, eine Klage bei der Kammer zur Beilegung von Streitigkeiten (Dispute Resolution Chamber) der FIFA einzureichen.
Mit Schreiben vom 25. Januar 2013 hielt A._ fest, dass der B._ FC in Verzug geraten sei, was er als Vertragsverletzung auffasse und weshalb er sich gestützt auf Art. 14 und 17 des FIFA-Reglements bezüglich Status und Transfer von Spielern ("Regulations for the Status and Transfer of Players"; Ausgabe 2012) von sämtlichen Verpflichtungen gegenüber dem Club befreit erachte.
B.
B.a. Am 5. Februar 2013 klagte A._ bei der Kammer zur Beilegung von Streitigkeiten der FIFA gegen den B._ FC auf Zahlung von insgesamt EUR 113'670.-- zuzüglich Verzugszins (davon EUR 52'000.-- ausstehender Lohn für die Monate Oktober 2012 bis Januar 2013 und EUR 52'000.-- Schadenersatz für entgangene Lohnzahlungen für die Monate Februar bis Mai 2013).
Mit Entscheid vom 6. November 2014 hiess die Kammer zur Beilegung von Streitigkeiten der FIFA die Klage im Umfang von EUR 26'520.--, zuzüglich Zins, gut.
B.b. Der Kläger focht den Entscheid der Kammer zur Beilegung von Streitigkeiten der FIFA vom 6. November 2014 beim Tribunal Arbitral du Sport (TAS) mit Berufung an.
Am 4. September 2015 fand in Lausanne eine mündliche Verhandlung statt.
Mit Schiedsentscheid vom 14. Januar 2016 hiess das TAS die Berufung des Klägers teilweise gut und änderte den angefochtenen Entscheid dahingehend ab, dass es den Beklagten zur Zahlung von EUR 54'753.--, zuzüglich Zins zu 5 % seit 5. Februar 2013, verurteilte.
C.
Mit Beschwerde in Zivilsachen beantragt der Kläger dem Bundesgericht, es sei der Schiedsentscheid des TAS vom 14. Januar 2016 aufzuheben und die Sache zu neuer Entscheidung an das Schiedsgericht zurückzuweisen.
Der Beschwerdegegner wie auch das TAS haben auf eine Vernehmlassung verzichtet.

Erwägungen:
1.
Nach <ref-law> ergeht der Entscheid des Bundesgerichts in einer Amtssprache, in der Regel in jener des angefochtenen Entscheids. Wurde dieser Entscheid in einer anderen Sprache abgefasst, bedient sich das Bundesgericht der von den Parteien verwendeten Amtssprache. Der angefochtene Entscheid ist in englischer Sprache abgefasst. Da es sich dabei nicht um eine Amtssprache handelt, ergeht der Entscheid des Bundesgerichts praxisgemäss in der Sprache der Beschwerde.
2.
Im Bereich der internationalen Schiedsgerichtsbarkeit ist die Beschwerde in Zivilsachen unter den Voraussetzungen der Art. 190-192 IPRG (SR 291) zulässig (<ref-law>).
2.1. Der Sitz des Schiedsgerichts befindet sich vorliegend in Lausanne. Die Parteien hatten im massgebenden Zeitpunkt ihren Sitz bzw. Wohnsitz ausserhalb der Schweiz (<ref-law>). Da sie die Geltung des 12. Kapitels des IPRG nicht ausdrücklich ausgeschlossen haben, gelangen die Bestimmungen dieses Kapitels zur Anwendung (<ref-law>).
2.2. Zulässig sind allein die Rügen, die in <ref-law> abschliessend aufgezählt sind (<ref-ruling> E. 5 S. 187; <ref-ruling> E. 1a S. 53; <ref-ruling> E. 1a S. 282). Nach <ref-law> prüft das Bundesgericht nur die Rügen, die in der Beschwerde vorgebracht und begründet worden sind; dies entspricht der in <ref-law> für die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht vorgesehenen Rügepflicht (<ref-ruling> E. 5 S. 187 mit Hinweis). Appellatorische Kritik ist unzulässig (<ref-ruling> E. 3.1 S. 567; <ref-ruling> E. 3b S. 382).
2.3. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den das Schiedsgericht festgestellt hat (<ref-law>). 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 (<ref-ruling> 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 <ref-law> beruht (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> sowie <ref-law> 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 <ref-law> vorgebracht oder ausnahmsweise Noven berücksichtigt werden (<ref-ruling> E. 2.2.1 S. 34; <ref-ruling> E. 3.1 S. 567; <ref-ruling> 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 Aktenhinweisen darzulegen, dass entsprechende Sachbehauptungen bereits im schiedsgerichtlichen Verfahren prozesskonform aufgestellt worden sind (vgl. <ref-ruling> E. 2a S. 486; <ref-ruling> E. 1c S. 473; je mit Hinweisen).
2.4. Soweit der Beschwerdeführer vor Bundesgericht die Unabhängigkeit des TAS bzw. die Unparteilichkeit der Schiedsrichter (<ref-law>) oder die Gültigkeit der Schiedsvereinbarung (<ref-law>) in Frage stellt, haben seine Vorbringen unbeachtet zu bleiben. Nach dem Grundsatz von Treu und Glauben ist ein solcher Einwand im Schiedsverfahren sofort geltend zu machen, ansonsten der Anspruch auf Anrufung des Beschwerdegrunds verwirkt (<ref-ruling> E. 3.1 S. 449 mit Hinweisen). Der Beschwerdeführer hat das TAS selber angerufen, ohne im Schiedsverfahren entsprechende Einwände zu erheben. Ebenso wenig hatte er im Schiedsverfahren gerügt, das Verfahren laufe nicht fair ab. Unter diesen Umständen ist es mit dem Grundsatz von Treu und Glauben nicht zu vereinbaren, diese Fragen im Rahmen des Beschwerdeverfahrens vor Bundesgericht erstmals aufzuwerfen.
Der Beschwerdeführer verlangt im gleichen Zusammenhang zu Unrecht unter Berufung auf das Recht auf ein faires Verfahren und die Rechtsweggarantie nach Art. 6 Ziff. 1 EMRK eine Erweiterung der Prüfungsbefugnis, indem er beanstandet, dass das Bundesgericht im Rahmen einer Schiedsbeschwerde nach <ref-law> die Rüge der falschen Rechtsanwendung und der offensichtlich falschen Feststellung des Sachverhalts nicht prüfen kann (vgl. Urteile 4A_178/2014 vom 11. Juni 2014 E. 2.4; 4A_198/2012 vom 14. Dezember 2012 E. 3.1; 4A_43/2010 vom 29. Juli 2010 E. 3.6.1; 4A_612/2009 vom 10. Februar 2010 E. 2.4.1). Er verkennt, dass die eingeschränkte Kognition nach <ref-law> in Verbindung mit <ref-law> für sämtliche Verfahren der internationalen Schiedsgerichtsbarkeit gilt, so auch, wenn der Rechtsstreit das Arbeitsverhältnis eines Sportlers betrifft.
3.
Der Beschwerdeführer wirft dem Schiedsgericht eine Verletzung des materiellen Ordre public (<ref-law>) vor.
3.1. Das Schiedsgericht hielt fest, der Beschwerdeführer habe das Arbeitsverhältnis mit dem Beschwerdegegner mit Schreiben vom 25. Januar 2013 einseitig fristlos aufgelöst. Es prüfte, ob diese Vertragsauflösung nach Art. 14 des FIFA-Reglements bezüglich Status und Transfer von Spielern zulässigerweise erfolgte. Die Bestimmung lautet wie folgt:
"A contract may be terminated by either party without consequences of any kind (either payment of compensation or imposition of sporting sanctions) where there is just cause."
Das Schiedsgericht erwog, im Zeitpunkt der Vertragsauflösung vom 25. Januar 2013 habe keine hinreichend schwere Vertragsverletzung seitens des Beschwerdegegners vorgelegen, die eine fristlose Vertragsauflösung gerechtfertigt hätte. Unter Berücksichtigung der vom Beschwerdeführer ausgestellten Empfangsbestätigung wie auch seines nachträglichen Verhaltens hielt es zunächst dafür, die vom Beschwerdegegner am 28. September 2012 geleistete Zahlung von EUR 28'075.-- habe in dem Sinne befreiend gewirkt, dass für die Zeitdauer bis 30. September 2012 keine weiteren Leistungen geschuldet seien. Der Arbeitsvertrag vom 22. Juni 2011 und die Zusatzvereinbarung vom 23. Juni 2011 seien zudem dahingehend auszulegen, dass die monatlichen Lohnzahlungen zwar jeweils am letzten Tag jeden Monats zur Zahlung fällig werden, dass jedoch eine spätere Zahlung keine Vertragsverletzung darstelle, sofern sie innerhalb der vertraglich vorgesehenen Schonfrist ( "grace period") von 90 Tagen erfolge. Das Ausbleiben der Lohnzahlung für die Monate Oktober, November und Dezember 2012 habe daher im massgebenden Zeitpunkt vom 25. Januar 2013 noch keine Vertragsverletzung dargestellt, die eine fristlose Kündigung aus wichtigem Grund gerechtfertigt hätte.
Zudem rechtfertigten die ausstehenden Entschädigungen für Wohnungs- und Automiete sowie Flugtickets für die Monate Oktober, November und Dezember 2012, die geringfügig gewesen seien, keine fristlose Kündigung. Weitere Gründe für die fristlose Kündigung habe der Beschwerdeführer nicht vorgebracht. Entsprechend stehe ihm, der das Arbeitsverhältnis ohne wichtigen Grund aufgelöst habe, kein Schadenersatzanspruch für entgangene Lohnzahlungen für die Monate Februar bis Mai 2013 zu. Demgegenüber sei für die Zeitdauer vom 1. Oktober 2012 bis zur Kündigung vom 25. Januar 2013 der Lohn von EUR 49'483.-- und eine Spesenentschädigung von EUR 5'270.-- geschuldet, womit dem Beschwerdeführer ein Gesamtbetrag von EUR 54'753.-- zuzüglich Zins zustehe.
3.2.
3.2.1. Die materiellrechtliche Überprüfung eines internationalen Schiedsentscheids durch das Bundesgericht ist auf die Frage beschränkt, ob der Schiedsspruch mit dem Ordre public vereinbar ist (<ref-ruling> E. 3a S. 333). Gegen den Ordre public verstösst die materielle Beurteilung eines streitigen Anspruchs nur, wenn sie fundamentale Rechtsgrundsätze verkennt und daher mit der wesentlichen, weitgehend anerkannten Wertordnung schlechthin unvereinbar ist, die nach in der Schweiz herrschender Auffassung Grundlage jeder Rechtsordnung bilden sollte. Zu diesen Grundsätzen gehören die Vertragstreue ( pacta sunt servanda), das Rechtsmissbrauchsverbot, der Grundsatz von Treu und Glauben, das Verbot der entschädigungslosen Enteignung, das Diskriminierungsverbot, der Schutz von Handlungsunfähigen und das Verbot übermässiger Bindung (vgl. <ref-law>), wenn diese eine offensichtliche und schwerwiegende Persönlichkeitsverletzung darstellt. Zur Aufhebung des angefochtenen Schiedsentscheids kommt es nur, wenn dieser nicht nur in der Begründung, sondern auch im Ergebnis dem Ordre public widerspricht (<ref-ruling> E. 4.1 sowie E. 4.3.1/4.3.2; <ref-ruling> E. 2.2 S. 392 ff.; je mit Hinweisen).
3.2.2. Der Beschwerdeführer verkennt zunächst den Begriff des materiellen Ordre public nach <ref-law>, indem er unter Hinweis auf <ref-law> und Art. L.3242-1 des französischen Arbeitsgesetzes (Code du travail) ausführt, das schweizerische und das französische Recht kennten zwingende Bestimmungen zur Fälligkeit der Lohnzahlung. Der Umstand, dass eine gesetzliche Bestimmung zwingend ist und die Parteien nicht durch Parteivereinbarung davon abweichen können, bedeutet nicht, dass diese dem Ordre public im Sinne von <ref-law> angehört und ihre Verletzung vom Bundesgericht frei zu prüfen wäre (vgl. BGE <ref-ruling> E. 2.2.2 S. 394; Urteile 4A_510/2015 vom 8. März 2016 E. 6.2.2; 4A_319/2015 vom 5. Januar 2016 E. 4.2.2; 4A_634/2014 vom 21. Mai 2015 E. 5.2.2). Zudem äussert sich der vom Beschwerdeführer erwähnte Art. 14 des FIFA-Reglements bezüglich Status und Transfer von Spielern nicht zum Zeitpunkt der Fälligkeit der Lohnforderung oder der Zulässigkeit einer entsprechenden Parteiabrede. Die zitierte Kommentarstelle, die ein Beispiel für eine zulässige fristlose Kündigung aufführt ("Example 1: A player has not been paid his salary for over 3 months. [...]"), spricht im Übrigen gerade gegen den in der Beschwerde vertretenen Standpunkt, wonach eine fristlose Kündigung im konkreten Fall am 25. Januar 2013 zulässig gewesen sei, weil zu diesem Zeitpunkt noch keine drei Monate (seit der Fälligkeit vom 31. Oktober 2012) vergangen waren. Auch der vom Beschwerdeführer erwähnte Art. 12 des Übereinkommens Nr. 95 der Internationalen Arbeitsorganisation über den Lohnschutz von 1949, das von der Schweiz nicht ratifiziert worden ist, äussert sich nicht zum Fälligkeitszeitpunkt, geschweige denn zur Kündigungsmöglichkeit des Arbeitnehmers, sondern sieht vor, dass der Lohn "in regelmässigen Abständen gezahlt werden [muss]".
Ebenso wenig vermag der Beschwerdeführer mit dem blossen Hinweis darauf, dass nach schweizerischem Recht der Arbeitsvertrag wegen wiederholten Zahlungsverzugs nach <ref-law> fristlos gekündigt werden könne und dies zu einem Schadenersatzanspruch nach <ref-law> führe, einen dem Ordre public im Sinne von <ref-law> angehörenden fundamentalen Rechtsgrundsatz aufzuzeigen, der im konkreten Fall vom Schiedsgericht missachtet worden wäre. Mit seinen allgemeinen Vorbringen zu <ref-law> vermag er ausserdem nicht darzutun, inwiefern im konkreten Fall eine Persönlichkeitsverletzung vorliegen würde, die mit dem Ordre public unvereinbar wäre.
3.2.3. Unter dem Titel "Verletzung des materiellen Ordre public im vorliegenden Fall" zitiert der Beschwerdeführer über mehrere Seiten aus dem Arbeitsvertrag vom 22. Juni 2011 und der Zusatzvereinbarung vom 23. Juni 2011 sowie der Begründung des angefochtenen Schiedsspruchs. Dabei verkennt er zunächst die Tragweite des Rechtsmissbrauchsverbots im Rahmen des Beschwerdegrunds von <ref-law>, indem er den schiedsgerichtlichen Erwägungen zur rechtlichen Bedeutung der vereinbarten Schonfrist ("grace period") seine eigene Ansicht gegenüberstellt, wonach eine solche unzulässig sei bzw. nicht dazu führen könne, dass eine fristlose Kündigung infolge Zahlungsverzugs während dieser Frist ausser Betracht bleibe. Das Schiedsgericht hat die vom Beschwerdeführer vertretene Rechtsauffassung, wonach ein unabdingbares Recht auf sofortige fristlose Kündigung bestehe, sobald ein fälliger Lohnanspruch unbezahlt geblieben ist, nicht geteilt. Darin ist keine Missachtung des Rechtsmissbrauchsverbots zu erblicken.
Der Beschwerdeführer führt zwar eine übermässige Bindung bzw. eine schwere Einschränkung der wirtschaftlichen Freiheit ins Feld, die ihn einer Zwangsarbeitssituation bzw. der Sklaverei ausgesetzt habe, vermag diese Behauptung jedoch durch keine schiedsgerichtlich festgestellten Sachverhaltselemente zu bekräftigen. Er bringt lediglich vor, er sei zur Deckung seines Lebensunterhalts auf seinen Lohn und die Spesenentschädigung angewiesen gewesen. Nachdem im Zeitpunkt der Kündigung die fälligen Lohn- und Spesenzahlungen bis auf die Monate Oktober bis Dezember 2012 bezahlt worden waren, konnten sich die vorgebrachten Liquiditätsprobleme einzig auf die anfängliche Verzögerung der Zahlungen beziehen. Auf den Umstand, dass ihm bereits für den Vertragsabschluss ein Einstiegsbonus ("signing-on fee") von EUR 30'000.-- und für die Saison 2012/2013 ein weiterer Bonus von EUR 20'000.-- ausbezahlt worden war, was annähernd fünf Monatslöhnen entsprach, geht der Beschwerdeführer mit keinem Wort ein. Seine weiteren Vorbringen sind zudem rein appellatorisch.
Eine offensichtliche und schwerwiegende Persönlichkeitsverletzung, die zur Ordre public-Widrigkeit des entsprechenden Schiedsentscheids führen würde (<ref-ruling> E. 4.3.1 und 4.3.2), liegt entgegen der in der Beschwerde vertretenen Ansicht nicht vor.
4.
Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kostenpflichtig (<ref-law>). Der Beschwerdegegner hat keinen Anspruch auf eine Parteientschädigung, da ihm aus dem bundesgerichtlichen Verfahren kein Aufwand erwachsen ist (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3.
Es wird keine Parteientschädigung zugesprochen.
4.
Dieses Urteil wird den Parteien und dem Tribunal Arbitral du Sport (TAS) schriftlich mitgeteilt.
Lausanne, 30. Juni 2016
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Leemann