Sachverhalt:
A.
Der Club A._ (Beklagter, Beschwerdeführer) ist ein Sportverein in U._, der dem Fussballverband U._angehört.
B._ (Kläger, Beschwerdegegner) ist rumänischer Staatsangehöriger und professioneller Fussballtrainer.
Am 9. Dezember 2015 unterzeichneten der Beklagte, der Kläger sowie C._ einen Vertrag. Darin verpflichtete sich der Beklagte, den Kläger als "Head Coach" sowie den technischen Stab für die erste Mannschaft zu ernennen.
Artikel 1 des Vertrags lautet:
"The duration of the contract shall be of 2 (two) years and 6 (six) months effective from 15/12/2015 to 15/06/2018."
In Bezug auf die Entlöhnung sieht Artikel 3 des Vertrags Folgendes vor:
"The [Club A._] undertakes to remunerate [B._] with a total amount of 7.370.000 EUR [...] net payable as follows:
- 500.000 EUR net as advance payment on 15/12/2015;
- 360.000 EUR net will be paid on 01/03/2016;
- [10 further payments of amounts between 360.000 and 600.000 EUR on dates from 01/03/2016 to 01/05/2018, including a payment of 450.000 EUR on 1 August 2016]
- The rest of the amount (2.100.000 EUR net) will be divided as monthly salary (70.000 EUR net per month), payable on the 5th of each month, starting with January 2016.
-..]
All amounts due by the Club under the present contract will be paid NET. This means that all the fees, taxes, contributions, generated by the net income obtained according to the present contract will be paid by the [Club A._]."
Artikel 10 des Vertrags enthält unter dem Titel "Breaking the Contract" in litera a und b sodann folgende Konventionalstrafen:
"a) If the [Club A._] terminates this Contract without just cause before 15.06.2018, or if [B._] will terminate the contract with just cause before 15.06.2018, then [B._] will receive from the [Club A._] a compensation equivalent to total value of the remaining duration of the contract, including the bonuses provided at Article Five (pro rata on a time basis, in case that they were not achieved by [B._] in full);
b) If [B._] terminates this Contract without just cause before 15.06.2018 then the [Club A._] shall be entitled to receive from him a compensation equivalent to the total value of the remaining duration of the contrat; [...]."
Mit Schreiben vom 10. Juli 2016 beendete der Kläger das Vertragsverhältnis und begründete dies mit Vertragsverletzungen des Beklagten.
B.
Am 21. Juli 2016 erhob der Kläger beim Tribunal Arbitral du Sport (TAS) Schiedsklage gegen den Beklagten. Er beantragte, der Beklagte sei zu verurteilen, ihm einerseits EUR 1'070'000.-- "net" als Lohnrückstände des Vertrags vom 9. Dezember 2015 und andererseits EUR 6'020'000.-- "net" als Schadenersatz für die Beendigung dieses Vertrags, zuzüglich Zins zu 5 % seit 10. September 2016, zu bezahlen.
Mit Schiedsentscheid vom 8. August 2017 hiess das TAS die Schiedsklage teilweise gut. Es verurteilte den Beklagten, dem Kläger EUR 5'570'000.--, bestehend aus den separaten Beträgen EUR 1'070'000.-- "NET" und EUR 4'500'000.-- "NET", (Dispositiv-Ziffer 2) sowie Zins zu 5 % auf den Betrag von EUR 4'500'000.-- seit 10. September 2016 (Dispositiv-Ziffer 3) zu bezahlen.
Der Schiedsentscheid hält für Zwecke der Zinsberechnung im Sinne von Dispositiv-Ziffer 3 weiter fest, dass Zahlungen des Beklagten an den Kläger zunächst auf den Betrag von EUR 1'070'000.-- angerechnet werden, bevor sie als (Teil-) Zahlung des Betrags von EUR 4'500'000.-- betrachtet werden (Dispositiv-Ziffer 4).
Schliesslich verurteilte das TAS den Beklagten, den Kläger entsprechend Artikel 3 des Vertrags vom 9. Dezember 2015 für sämtliche Gebühren, Steuern und Abgaben ("all fees, taxes and contributions") schadlos zu halten, welche diesem aus den Zahlungen des Beklagten gemäss Dispositiv-Ziffer 2 erwachsen (Dispositiv-Ziffer 5).
C.
Der Beschwerdeführer verlangt mit Beschwerde in Zivilsachen, der Schiedsentscheid vom 8. August 2017 sei aufzuheben und die Streitsache sei zur Neubeurteilung an das TAS zurückzuweisen.
Der Beschwerdegegner beantragt, die Beschwerde sei abzuweisen, soweit auf sie einzutreten ist. Das TAS schliesst in seiner Vernehmlassung auf Abweisung der Beschwerde.

Erwägungen:
1.
Nach <ref-law> ergeht der Entscheid des Bundesgerichts in einer Amtssprache, in der Regel 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 die Parteien ihre dem Bundesgericht eingereichten Rechtsschriften in Übereinstimmung mit <ref-law> i.V.m. <ref-law> auf Deutsch (Beschwerdeführer) und auf Französisch (Beschwerdegegner) verfassten, ergeht der Entscheid des Bundesgerichts praxisgemäss in der Sprache der Beschwerde (<ref-ruling> E. 1).
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 beziehungsweise 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. Der Entscheid kann nur aus einem der in <ref-law> abschliessend aufgezählten Gründe angefochten werden (<ref-ruling> E. 5; <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 mit Hinweis). Appellatorische Kritik ist unzulässig (siehe <ref-ruling> E. 3.1; <ref-ruling> E. 3b).
3.
Der Beschwerdeführer rügt, das Schiedsgericht habe über Streitpunkte entschieden, die ihm nicht unterbreitet worden seien (<ref-law>).
3.1. Gemäss <ref-law> kann entsprechend der französischen Fassung des Gesetzestexts gegen einen Schiedsentscheid eingewendet werden, das Schiedsgericht habe einer Partei mehr oder anderes zugesprochen, als verlangt worden sei (<ref-ruling> E. 3a S. 175; <ref-ruling> E. 3a S. 642).
Nach der bundesgerichtlichen Rechtsprechung liegt keine Verletzung des Grundsatzes "ne eat iudex ultra petita partium" vor, wenn der eingeklagte Anspruch in rechtlicher Hinsicht ganz oder teilweise abweichend von den Begründungen der Parteien gewürdigt wird, sofern er vom Rechtsbegehren gedeckt ist (<ref-ruling> E. 3a S. 175; Urteile 4A_50/2017 vom 11. Juli 2017 E. 3.1; 4A_678/2015 vom 22. März 2016 E. 3.2.1; je mit Hinweisen; vgl. auch <ref-ruling> E. 5 S. 39). Das Schiedsgericht ist aber an den Gegenstand und Umfang des Begehrens gebunden, insbesondere wenn der Kläger seine Ansprüche im Rechtsbegehren selbst qualifiziert oder beschränkt (Urteile 4A_50/2017 vom 11. Juli 2017 E. 3.1; 4A_678/2015 vom 22. März 2016 E. 3.2.1; je mit Hinweisen).
3.2. Der Beschwerdeführer bringt vor, das Schiedsgericht habe ihn in Dispositiv-Ziffer 5 zur Zahlung sämtlicher Gebühren, Steuern und Abgaben, die durch die Zahlungen gemäss Dispositiv-Ziffer 2 verursacht werden, verurteilt. Dies habe der Beschwerdegegner im Schiedsverfahren jedoch nicht verlangt. Aus diesem Grund verletze der Schiedsentscheid den Grundsatz "ne eat iudex ultra petita partium".
Die Klagebegehren lauteten auf Zahlung von EUR 1'070'000.-- "netto" ("net") beziehungsweise EUR 6'020'000.-- "netto" ("net"). Wie das Schiedsgericht zu Recht festhielt, wird damit Artikel 3 des Vertrags vom 9. Dezember 2015 abgebildet, wonach sämtliche vom Beschwerdeführer an den Beschwerdegegner geschuldeten Beträge "netto" zu bezahlen seien. Artikel 3 in fine definiert sodann, was unter "netto" zu verstehen ist, nämlich dass sämtliche Gebühren, Steuern und Abgaben, die durch das Nettoeinkommen gemäss Vertrag verursacht werden, durch den Beschwerdeführer zu bezahlen sind. Das Klagebegehren 1 nahm ausdrücklich auf den Vertrag vom 9. Dezember 2015 Bezug. Auch aus der Begründung der Schiedsklage ("it is based on art. 3 of the contract signed with the club on 09.12.2015" bzw. "it is founded on art. 10 [...] corroborated with art. 3 [...] of the contract") wird deutlich, dass die Klagebegehren auf Artikel 3 des Vertrags gestützt werden. Damit hat der Beschwerdegegner mit seinen Klagebegehren, jedenfalls im Lichte der Begründung interpretiert (Urteil 4A_440/2010 vom 7. Januar 2011 E. 3.2.1, nicht publ. in: <ref-ruling>; vgl. auch Urteil 5A_527/2016 vom 16. November 2016 E. 3.3.1 [zu <ref-law>]), zum Ausdruck gebracht, dass der Beschwerdeführer auch zur Zahlung der genannten Gebühren, Steuern und Abgaben verurteilt werden soll.
3.3. Weiter meint der Beschwerdeführer, Dispositiv-Ziffer 4 des Schiedsentscheids, wonach Teilzahlungen zunächst "an die (nicht zinsgesicherte) Teilforderung" in Höhe von EUR 1'070'000.-- angerechnet werden, weiche "vom Grundsatz des <ref-law> ab, wonach im Falle von Teilzahlungen der Schuldner berechtigt ist, festzulegen, auf welche Teilschuld die jeweiligen Zahlungen anzurechnen seien". Auch diese Anordnung sei nicht durch einen entsprechenden Antrag des Beschwerdegegners im Schiedsverfahren gedeckt.
Es leuchtet nicht ein, inwiefern das Schiedsgericht dem Beschwerdegegner in Dispositiv-Ziffer 4 mehr oder anderes zugesprochen hätte, als dieser verlangt hatte. Es legte vielmehr eine Tilgungsreihenfolge fest, die - wie der Beschwerdeführer zu Recht festhält - im Ergebnis dazu führt, dass die auf den Betrag von EUR 4'500'000.-- geschuldeten Zinsen auch dann weiter anfallen, wenn der Beschwerdeführer den Betrag von EUR 1'070'000.-- bezahlt haben sollte. Das Schiedsgericht hat insofern in die Berechnung des Zinsenlaufs eingegriffen (vgl. Urteil 4P.183/1989 vom 19. Februar 1990 E. 11b, in: ASA Bull. 1990 S. 171 ff.; zustimmend Andreas Bucher, in: Commentaire romand, Loi sur le droit international privé - Convention de Lugano, 2011, N. 79 zu <ref-law>), überschreitet aber den vom Beschwerdegegner anbegehrten Zins von 5 % nicht. Auch der zugesprochene Betrag von EUR 5'570'000.-- bleibt hinter den gemäss Klagebegehren verlangten EUR 7'090'000.-- zurück und bewegt sich damit im Rahmen der Rechtsbegehren.
3.4. Entsprechend hat das Schiedsgericht dem Beschwerdegegner weder mehr noch anderes zugesprochen, als dieser verlangte. Der Beschwerdegrund von <ref-law> ist damit entgegen dem Beschwerdeführer nicht gegeben.
4.
Der Beschwerdeführer wirft dem Schiedsgericht ferner eine Verletzung des materiellen Ordre public (<ref-law>) vor.
4.1. Er kritisiert, die vom Schiedsgericht auferlegte Konventionalstrafe in Höhe von EUR 4'500'000.-- schränke seine wirtschaftliche Freiheit "ganz offensichtlich übermässig ein". Sie erscheine "nahezu absurd", wenn man bedenke, dass sie mehr als das 18-fache des durchschnittlichen Monatslohns des Beschwerdegegners von EUR 245'666.66 betrage. Ausserdem übersteige sie bei weitem den Betrag, "den der Gesetzgeber in <ref-law> als Höchstbetrag einer zulässigen Strafzahlung bei der Kündigung eines Arbeitsvertrags festlegte". Hinzu komme, dass sich der Beschwerdegegner "mit Zusprechung dieser Konventionalstrafe offensichtlich bereichern" würde, komme er doch faktisch während 18 Monaten in den Genuss eines Lohns, ohne dass er arbeitsvertraglich an den Beschwerdeführer gebunden bliebe. Damit könne er ohne Weiteres einer neuen Beschäftigung nachgehen, ohne sich den dabei erzielten Verdienst anrechnen lassen zu müssen. Gerade dies verlange aber <ref-law>.
4.2. Es erscheint fraglich, ob der Beschwerdeführer mit diesen Ausführungen den im bundesgerichtlichen Verfahren geltenden Begründungsanforderungen genügt (siehe Art. 77 Abs. 3 in Verbindung mit <ref-law>). Dafür wäre unerlässlich, dass auf die Begründung des angefochtenen Entscheids eingegangen und im Einzelnen aufgezeigt wird, worin eine vom Bundesgericht überprüfbare Rechtsverletzung liegt (<ref-ruling> E. 2 S. 116, 86 E. 2 S. 89). Das Schiedsgericht hat in den Ziffern 60 bis 89 des Schiedsentscheids ausführlich geprüft, ob und in welchem Umfang die Konventionalstrafe in Anwendung von <ref-law> herabzusetzen ist. Der Beschwerdeführer setzt sich damit in seiner Beschwerde an das Bundesgericht nicht auseinander, sondern hält den Erwägungen des Schiedsentscheids lediglich in appellatorischer Weise seine eigene Würdigung gegenüber, wenn er behauptet, seine wirtschaftliche Freiheit werde "offensichtlich übermässig" eingeschränkt. Die Rüge ist aber ohnehin unbegründet:
4.3. Der Ordre public (<ref-law>) hat sowohl einen materiellen als auch einen verfahrensrechtlichen Gehalt. 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. Diese Aufzählung ist jedoch nicht abschliessend (<ref-ruling> E. 4.1 sowie E. 4.3.1 und 4.3.2 mit Hinweisen).
4.4. Gemäss <ref-law> hat der Richter übermässig hohe Konventionalstrafen nach seinem Ermessen herabzusetzen. Nach der Rechtsprechung des Bundesgerichts handelt es sich dabei um eine Norm des ordre public, mithin um eine zwingende Norm, die der Richter selbst dann anzuwenden hat, wenn der Schuldner die Herabsetzung nicht ausdrücklich verlangt hat (dazu kürzlich ausführlich <ref-ruling> E. 4.1 S. 2 mit Hinweisen). Entgegen der Auffassung des Beschwerdeführers bedeutet dies aber nicht, dass eine Verletzung von <ref-law> gegen den Ordre public im Sinne von <ref-law> verstösst (Urteile 4A_312/2017 vom 27. November 2017 E. 3.3.3; 4A_536/2016 und 4A_540/2016 vom 26. Oktober 2016 E. 4.3.2; 4A_510/2015 vom 8. März 2016 E. 6.2.2; 4A_634/2014 vom 21. Mai 2015 E. 5.2.2; vgl. auch Urteil 4P.88/2016 vom 10. Juli 2006 E. 5). Das Bundesgericht hat mehrfach festgehalten, dass es Schiedsentscheide nicht mit Bezug auf <ref-law> überprüft, als wäre es eine Appellationsinstanz (Urteile 4A_510/2015 vom 8. März 2015 E. 6.2.2; 4A_634/2014 vom 21. Mai 2015 E. 5.2.2). Soweit der Beschwerdeführer dies verkennt und mit seinen Ausführungen zu der nach seiner Ansicht übermässigen Höhe der vereinbarten Konventionalstrafe unzulässige inhaltliche Kritik am angefochtenen Schiedsentscheid übt, ist er nicht zu hören.
Der Beschwerdeführer führt eine angeblich übermässige vertragliche Einschränkung seiner wirtschaftlichen Freiheit ins Feld. Dies setzt nach schweizerischem Verständnis voraus, dass der Verpflichtete der Willkür eines anderen ausgeliefert, seine wirtschaftliche Freiheit aufgehoben oder in einem Masse eingeschränkt wird, dass die Grundlagen seiner wirtschaftlichen Existenz gefährdet sind (<ref-ruling> E. 5.4; <ref-ruling> E. 4.3.2). Inwiefern dies der Fall sein soll, zeigt der Beschwerdeführer nicht ansatzweise auf. Dies gilt erst recht für die Frage, aus welchen Gründen die vertraglich vereinbarte Konventionalstrafe gar eine offensichtliche und schwerwiegende Persönlichkeitsverletzung darstellen soll, die zur Ordre-public-Widrigkeit des Schiedsentscheids führen könnte.
Der Beschwerdeführer behauptet im Wesentlichen, eine Konventionalstrafe, welche das 18-fache eines Monatslohns betrage, erscheine "nahezu absurd". Das Schiedsgericht hat dagegen die Vertragsverletzung des Beschwerdeführers berücksichtigt, die es als schwer einstufte. Der Beschwerdeführer habe seine vertraglichen Pflichten beinahe vollständig nicht erfüllt, und dies fast ab Beginn der Vertragsdauer. Der Beschwerdegegner hingegen müsse sich kein Verhalten vorwerfen lassen, das zu einer Herabsetzung der Konventionalstrafe Anlass gebe. Ausserdem sei zu berücksichtigen, dass die Beschäftigungslosigkeit (sei sie nun bezahlt oder nicht) für einen Fussballtrainer grundsätzlich unwillkommen ist, da dieser durch seine Tätigkeit an Renommee und Erfahrung gewinne. Jedenfalls ist im Umstand allein, dass eine Konventionalstrafe das 18-fache eines Monatslohns beträgt, keine Verletzung des Ordre public zu sehen, zumal der Vertrag vorsieht, dass (bei Vorliegen der entsprechenden Voraussetzungen) auch der Beschwerdeführer zu einer Konventionalstrafe in dieser Höhe berechtigt gewesen wäre und - wie das Schiedsgericht feststellte und von keiner Partei bestritten wurde - das Stärkeverhältnis zwischen den Parteien in Bezug auf die wirtschaftliche Kraft und die Geschäftserfahrenheit ausgeglichen war (vgl. auch Urteil 4A_510/2015 vom 8. März 2016 E. 6.2.2).
Der Hinweis auf die gesetzgeberischen Wertungen in <ref-law> hilft dem Beschwerdeführer von vornherein nicht. Liegt der wichtige Grund zur fristlosen Auflösung des Arbeitsverhältnisses im vertragswidrigen Verhalten des Arbeitgebers, wie dies vorliegend der Fall ist, so hat dieser dem Arbeitnehmer vollen Schadenersatz nach <ref-law> für eine gerechtfertigte Auflösung zu leisten. Die Frage einer Entschädigung nach <ref-law> stellt sich ohnehin nur bei einer ungerechtfertigten Entlassung (<ref-ruling> E. 2.1.1 S. 305 mit Hinweisen). Ebenso wenig ist im Übrigen das vom Beschwerdeführer erhobene Argument der Bereicherung nachvollziehbar. Das Schiedsgericht hat dem Aspekt, dass der Beschwerdegegner einer neuen Beschäftigung nachgehen kann, vollumfänglich Rechnung getragen. Es erwog, dass die vorliegende Streitigkeit wohl keinen bedeutenden Einfluss auf die Stellenaussichten des Beschwerdegegners habe. Umgekehrt erkannte es, dass es nur sehr wenige Positionen als Trainer auf dem Niveau des Beschwerdegegners gebe. Es folgerte, dass es wahrscheinlich - wenn auch nicht sicher - sei, dass er innert 12 Monaten ab Vertragsbeendigung eine passende Stelle hätte finden können. Es ergänzte, dass es keineswegs gewiss sei, dass eine solche Stelle gleich gut wie die bisherige bezahlt sei. Das Schiedsgericht berücksichtigte diese Umstände im Ermessensentscheid und reduzierte die Konventionalstrafe von EUR 6'020'000.-- auf EUR 4'500'000.--. Abgesehen davon wäre mit einem blossen, aus der Konventionalstrafe resultierenden "Bereicherungseffekt" des Beschwerdegegners noch keine übermässige Einschränkung der wirtschaftlichen Freiheit des Beschwerdeführers dargetan. Die Kritik des Beschwerdeführers geht daher auch unter diesem Gesichtspunkt ins Leere.
Die Rüge, der angefochtene Schiedsentscheid sei mit dem Ordre public unvereinbar, ist somit unbegründet.
5.
Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kosten- und entschädigungspflichtig (siehe Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 25'000.-- werden dem Beschwerdeführer auferlegt.
3.
Der Beschwerdeführer hat den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 30'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Tribunal Arbitral du Sport (TAS) schriftlich mitgeteilt.
Lausanne, 29. Januar 2018
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Brugger