Sachverhalt: A. A.a. Der Club A._ (Kläger, Widerbeklagter, Beschwerdeführer) ist ein ägyptischer Fussballclub, der in der höchsten Liga Ägyptens spielt. Er ist Mitglied des ägyptischen Fussballverbands (Egyptian Football Association, EFA), der wiederum der Fédération Internationale de Football Association (FIFA) angehört. B._ (Beklagter, Widerkläger, Beschwerdegegner) war während der vorliegend massgebenden Zeit als professioneller Fussballspieler tätig. Er ist ghanaischer und britischer Staatsbürger. A.b. Am 2. Juli 2008 schlossen die Parteien einen Arbeitsvertrag für drei Spielsaisons ab, der unter anderem Folgendes vorsah: "The Club agreed that the Player will join football team for the total amount of: (only Three million four hundred thousands Euro) Distributed on the duration of the years of the contract. *First Season amount of: (one million Euro). Advance payment: amount of 250000 Euro represents 25% of the value of the contract for the season settled on 2/7/2008 & 50% on monthly ten instalments maximum settled as follows: First instalment: amount of (250000 Euro). (only two hundred and fifty thousands Euro settled on 5/7/2008) Second instalment: amount (250000 Euro). (only two hundred and fifty thousands Euro settled on 1/1/2009 ... & 25% settled at the end of the season according to the proportion of the participation of the player. In playing the proportion of 80% of the number of matches will be considered the rate which the player is due for these amounts (25%) completely. The entry of the Player in the list of the match is considered participation in it." Ebenfalls am 2. Juli 2008 schlossen die Parteien einen Zusatzvertrag ab, in dem unter anderem Folgendes festgehalten wurde: "2.1 The 25% dues of the Player settled at the end of each season as per the terms and conditions of the Contract shall be conditional upon the Player being available for participating in at least 80% of the matches in that season. "2.1 The 25% dues of the Player settled at the end of each season as per the terms and conditions of the Contract shall be conditional upon the Player being available for participating in at least 80% of the matches in that season. ... 2.4 Paragraph (8) of Clause Five of the Contract entitled 'Commitments of the Club towards the Player' shall be amended to read as follows: If the player does not receive his due instalment within 14 business days after the due date, the issue will be submitted to the committee of player affairs for its determination. If the player does not receive his due instalment within 14 business days after the due date, the issue will be submitted to the committee of player affairs for its determination. ... 2.8 The Player can get a house and a car of a reasonable choice to be paid for by the Club." A.c. Am 14. Juli 2008 zahlte der Club A._ dem Fussballspieler B._ einen Bruttobetrag von EUR 500'000.-- per Check, was - nach Abzug von Steuern von EUR 100'000.-- und einer Einschreibegebühr des Nationalverbands EFA von EUR 34'000.-- - einer Nettozahlung von EUR 366'000.-- entsprach. Zudem zahlte der Club A._ zunächst für den Aufenthalt in einem Hotel, anschliessend am 10. August 2008 EUR 24'000.-- für die Unterbringung in einer Wohnung. Am 24. September 2008 schloss B._ einen Mietvertrag für eine neue Wohnung für die Zeit vom 1. Oktober 2008 bis zum 30. September 2010 ab. B._ blieb im Oktober 2008 dem Training während mehrerer Tage fern. Am 11. Oktober 2008 nahm er für die Nationalmannschaft von Ghana an einem Qualifikationsspiel für die Weltmeisterschaft teil. Am 15. Oktober 2008 spielte er - gegen den Willen von Club A._ - im Rahmen eines Freundschaftsspiels gegen Südafrika. Für diese Abwesenheiten nahm der Club A._ einen Lohnabzug von EGP 75'000.-- vor. Am 17. Oktober 2008 fehlte B._ bei einem Meisterschaftsspiel. Am 26. Oktober 2008 spielte der Club A._ ein Meisterschaftsspiel gegen C._, an dem auch B._ teilnahm. Aufgrund der überaus schwachen Leistung und des mangelnden Einsatzes der ganzen Mannschaft sanktionierte der Club A._ sämtliche Spieler mit einem Abzug von 4 % des Jahreslohns; der auf B._ entfallende Lohnabzug betrug demnach EUR 40'000.--. Am 18. November 2008 wurde B._ aufgrund eines Fehlverhaltens anlässlich eines Fussballspiels vom 14. November 2008 für die drei darauffolgenden Spiele gesperrt und mit einer Busse von EGP 20'000.-- (entsprechend EUR 2'666.--) belegt, die von dem Club A._ direkt vom Lohn des Spielers abzuziehen und an die EFA zu überweisen war. Der Club A._ nahm aufgrund der verhängten Spielsperre zudem einen Lohnabzug von EUR 72'202.-- vor. In der Folge übergab der Fussballclub B._ mehrere Checks; es blieb aber strittig, ob und inwieweit damit die offenen Schulden beglichen wurden. Mitte März 2009 kehrte B._ nach Grossbritannien zurück. Mit Schreiben vom 28. März 2009 forderte sein Rechtsvertreter den Club A._ auf, die vertraglich geschuldeten Zahlungen bis spätestens 31. März 2009 zu leisten. Mit Schreiben vom 1. April 2009 teilte er dem Club A._ mit, den Arbeitsvertrag vom 2. Juli 2008 mit sofortiger Wirkung aufzulösen. A.d. Am 29. Mai 2009 klagte der Club A._ bei der Kammer zur Beilegung von Streitigkeiten (Dispute Resolution Chamber) der FIFA mit dem Antrag, B._ sei wegen ungerechtfertigter Vertragsauflösung zur Zahlung von EUR 3'408'892.40 zu verurteilen. Dieser erhob Widerklage und verlangte seinerseits EUR 3'467'460.-- für Zahlungsrückstände sowie Schadenersatz aus Vertragsverletzung. Mit Entscheid vom 28. Juni 2013 wies die Kammer zur Beilegung von Streitigkeiten der FIFA die Klage ab. Hingegen hiess sie die Widerklage teilweise gut und verurteilte den Club A._ zur Zahlung von EUR 189'767.-- für Zahlungsrückstände und EUR 1.4 Mio. Schadenersatz (jeweils zuzüglich Zins). B. Am 10. Dezember 2013 erhob der Club A._ beim Tribunal Arbitral du Sport (TAS) Berufung gegen den Entscheid der Kammer zur Beilegung von Streitigkeiten der FIFA vom 28. Juni 2013 mit den folgenden (im Laufe des Verfahrens angepassten) Rechtsbegehren: "A). To fully accept the present appeal against the Decision of the FIFA Dispute Resolution Chamber dated 28 June 2013. B). Consequently, to adopt an award annulling said decision and declaring that: 1). The appealed Decision passed on 28 June 2013 in Zurich, Switzerland, is fully set aside and 2.1). The Player terminated with no just cause the Employment Contract it had signed with A._, 2.1.1). As consequence of the above to state that the Respondent shall not be entitled to receive any financial amount from the Appellant following to its termination of the Employment Contract. 2.1.2). As consequence of the above to order the Respondent to pay to the Appellant a compensation in the amount of 3,525,000.00 Euros (Three Million Five Hundred and Twenty-Five Thousand Euro only). OR, IN THE ALTERNATIVE 2.2) In the unlikely event that the Panel decides that the Appellant was in breach of contract, to mitigate the indemnification according to point 27 to 34 of the present Appeal Brief. C). To fix the sum of 20,000 CHF to be paid by the Respondent to the Appellant, to help the payment of its legal fees and costs. D). To condemn the Respondent to the payment of the whole CAS administra- tion costs and the Arbitrators fees. E). To order the Player to pay an additional 5% annual interest on the amounts due to the Appellant as from the date of the breach of the Employment Contract as from the date of the breach of the employment contract with no just cause, i.e. 1 April 2009." Mit Berufungsantwort vom 9. April 2014 beantragte der Widerkläger, es sei die Berufung abzuweisen und der angefochtene Entscheid zu bestätigen. Mit Schiedsentscheid vom 31. Oktober 2014 hiess das TAS die Berufung teilweise gut und ersetzte den angefochtenen Entscheid der Kammer zur Beilegung von Streitigkeiten der FIFA durch seinen Schiedsentscheid: Es stellte fest, dass B._ den Arbeitsvertrag am 1. April 2009 infolge der von dem Club A._ begangenen Vertragsverletzungen aus wichtigem Grund auflöste und verurteilte den Fussballclub zur Zahlung von EUR 152'799.-- und USD 30'000.-- für Zahlungsrückstände sowie von EUR 654'736.-- und USD 66'000.-- Schadenersatz aus Vertragsverletzung (jeweils zuzüglich Zins). Alle weiteren Anträge lehnte das Schiedsgericht ab. C. Mit Beschwerde in Zivilsachen beantragt der Club A._ dem Bundesgericht, es sei der Schiedsentscheid des TAS vom 31. Oktober 2014 aufzuheben und die Streitsache zu neuer Beurteilung an das Schiedsgericht zurückzuweisen. Der Beschwerdegegner beantragt, es sei auf die Beschwerde nicht einzutreten; eventualiter sei diese abzuweisen. Das TAS beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Der Beschwerdeführer hat dem Bundesgericht eine Replik, der Beschwerdegegner eine Duplik eingereicht.