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.