Sachverhalt:
A.
X._ tötete am 7. Mai 2015 A._ in seiner Wohnung mit 37 Messerstichen.
B.
Das Strafgericht des Kantons Basel-Stadt verurteilte X._ am 14. September 2016 wegen Mordes zu einer Freiheitsstrafe von 18 Jahren. Das Verfahren wegen mehrfachen Konsums von Betäubungsmitteln stellte es ein. Es behaftete X._ auf der Anerkennung der Schadenersatzforderung der Privatklägerin und verurteilte ihn, den beiden Privatklägern je eine zu verzinsende Genugtuung von Fr. 25'000.-- zu bezahlen. Es entschied über die beschlagnahmten Gegenstände und regelte die Kosten- sowie Entschädigungsfolgen.
C.
Gegen dieses Urteil erhob X._ am 14. September 2016 Berufung. Am 16. Dezember 2016 erfolgte die Berufungserklärung, am 10. Februar 2017 die Berufungsbegründung seiner damaligen amtlichen Verteidigerin. X._ reichte in der Folge selbst einige Schreiben ein, worin er unter anderem um einen Wechsel seiner amtlichen Verteidigung ersuchte. Mit Eingabe vom 11. April 2017 bat auch seine damalige amtliche Verteidigerin darum, aus dem Mandat entlassen zu werden. Mit Verfügungen vom 19. April 2017 wurde diese aus ihrem Mandat entlassen und Advokat Dr. Nicolas Roulet als amtlicher Verteidiger von X._ eingesetzt.
Mit Urteil vom 6. Februar 2018 stellte das Appellationsgericht des Kantons Basel-Stadt fest, dass das Urteil des Strafgerichts bezüglich des Schuldspruchs wegen Mordes, der Einstellung des Verfahrens wegen mehrfachen Konsums von Betäubungsmitteln, des Zivilpunkts, der Verfügung über die beschlagnahmten Gegenstände und der Entschädigung des unentgeltlichen Vertreters der Privatkläger in Rechtskraft erwachsen ist. Es verurteilte X._ zu einer Freiheitsstrafe von 17 Jahren und regelte die Kosten- sowie Entschädigungsfolgen.
D.
X._ beantragt mit Beschwerde in Strafsachen, das appellationsgerichtliche Urteil sei vollumfänglich aufzuheben. Die Angelegenheit sei zur neuen Entscheidung im Sinne der Erwägungen an die Vorinstanz zurückzuweisen. Eventualiter sei er vom Vorwurf des Mordes freizusprechen und wegen Totschlags, eventualiter vorsätzlicher Tötung, zu verurteilen und es sei die Angelegenheit zur Festsetzung einer angemessenen Strafe an das Appellationsgericht zurückzuweisen. Er ersucht um unentgeltliche Rechtspflege und Verbeiständung.

Erwägungen:
1.
Nicht zu hören ist der Beschwerdeführer mit seiner persönlichen Eingabe vom 20. Mai 2018. Das begründete vorinstanzliche Urteil ging seinem Verteidiger am 3. April 2018 zu. Die 30-tägige Frist zur Einreichung der Beschwerde in Strafsachen endete am 8. Mai 2018 (vgl. Art. 100 Abs. 1 i.V.m. <ref-law>). Damit ist seine Eingabe verspätet.
2.
2.1. Der Beschwerdeführer rügt, die Vorinstanz schränke ihre Kognition bundesrechtswidrig auf die Strafzumessung ein. Damit verletze sie Art. 399 sowie 404 Abs. 2 StPO und unterschreite das ihr zustehende Ermessen beziehungsweise schöpfe dieses nicht vollumfänglich aus. Einerseits sei eine Beschränkung der Berufung auf den Strafpunkt vorliegend nicht zulässig. Andererseits stelle das erstinstanzliche Urteil einen gesetzeswidrigen und unbilligen Entscheid dar. In diesem Zusammenhang verletze die Vorinstanz Bundesrecht, indem sie den festgestellten Sachverhalt unter den Tatbestand des Mordes anstatt unter jenen des Totschlags, eventualiter der vorsätzlichen Tötung subsumiere. Das Tatbestandselement der Grausamkeit sei nicht bundesrechtskonform ausgelegt worden.
2.2. Hinsichtlich des Umfangs der Berufung stellt die Vorinstanz fest, die ursprüngliche amtliche Verteidigerin des Beschwerdeführers habe bereits in der Berufungserklärung festgehalten, dass sich die Berufung nur gegen die Strafzumessung richte und eine Reduktion der Strafe von 18 auf 12 Jahre gefordert werde. Auch in der Berufungsbegründung seien ausschliesslich Ausführungen zur Strafzumessung sowie zum Beweisantrag gemacht worden. Unter anderem sei festgehalten worden, es sei "innerhalb des Mordtatbestandes kein schweres Verschulden gegeben". Der Schuldspruch wegen Mordes sei ausdrücklich akzeptiert worden. Der neue Verteidiger habe jedoch in der Folge die Berufung in seiner Begründung auf den Schuldpunkt ausgedehnt, indem er das Rechtsbegehren gestellt habe, der Beschwerdeführer sei lediglich wegen Totschlags, eventualiter vorsätzlicher Tötung zu verurteilen und die Strafe entsprechend auf 43⁄4 Jahre zu reduzieren.
In rechtlicher Hinsicht erwägt die Vorinstanz gestützt auf die Literatur, <ref-law> stelle eine Einschränkung der im Rechtsmittelverfahren geltenden Dispositionsmaxime dar, weshalb von ihm nur zurückhaltend und insbesondere nur unter den gesetzlich erwähnten Voraussetzungen der Gesetzwidrigkeit und Unbilligkeit Gebrauch zu machen sei. Mit der Bestimmung sollten eindeutig unrichtige Urteile verhindert werden, bei welchen der Mangel klar zu Tage trete. Vorliegend sei das erstinstanzliche Urteil weder gesetzeswidrig noch unbillig. Wenn der Verteidiger geltend mache, der Beschwerdeführer sei sich der Grausamkeit seines Vorgehens nicht bewusst gewesen, was zur Verneinung des Mordvorsatzes hätte führen müssen, verkenne er, dass ein solches Bestreiten nicht per se dazu führe, dass der Mordtatbestand ausscheide. Vielmehr sei die Frage des Vorsatzes bei fehlendem Geständnis aufgrund der Umstände zu entscheiden. Die erste Instanz habe aufgrund der äusseren Umstände, vorwiegend der brutalen Art und Weise der Tatausführung und dem sich sehr lange hinziehenden Sterbevorgang des Opfers, die Tat auch unter dem subjektiven Aspekt als Mord qualifiziert. Dieses Vorgehen sei nicht zu beanstanden. Es liege somit kein Fall von <ref-law> vor, weshalb auf die rechtliche Qualifikation als Mord nicht mehr zurückzukommen sei (Urteil S. 5 ff.).
2.3. Im Berufungsverfahren gilt die Dispositionsmaxime (Urteile 6B_533/2016 vom 29. November 2016 E. 4.2; 6B_428/2013 vom 15. April 2014 E. 3.3). Der Berufungskläger muss in seiner Berufungserklärung angeben, ob er das Urteil vollumfänglich oder nur in Teilen anficht (<ref-law>). Ficht er nur Teile des Urteils an, hat er in der Berufungserklärung verbindlich anzugeben, auf welche Teile (Schuldpunkt, allenfalls bezogen auf einzelne Handlungen; Bemessung der Strafe; etc.) sich die Berufung beschränkt (<ref-law>). Das Berufungsgericht überprüft das erstinstanzliche Urteil nur in den angefochtenen Punkten (<ref-law>). Es kann zugunsten der beschuldigten Person auch nicht angefochtene Punkte überprüfen, um gesetzwidrige oder unbillige Entscheidungen zu verhindern (<ref-law>). Soweit die Einschränkung der Berufung auf einzelne Punkte eindeutig und der Grundsatz der Untrennbarkeit oder inneren Einheit nicht verletzt ist (vgl. zum früheren kantonalen Prozessrecht: <ref-ruling> E. 4b S. 105; <ref-ruling> E. 2c S. 109 f.; Urteil 6P.98/2005 vom 3. Februar 2006 E. 3.2; je mit Hinweisen; LUZIUS EUGSTER, in: Basler Kommentar, Schweizerische Strafprozessordnung, 2. Aufl. 2014, N. 6 und 8 zu <ref-law>), muss die Einschränkung durch das Berufungsgericht respektiert werden (Urteile 6B_769/2016 vom 11. Januar 2017 E. 2.3; 6B_349/2016 vom 13. Dezember 2016 E. 2.3; 6B_634/2012 vom 11. April 2013 E. 2.3.1; je mit Hinweisen). Die nicht angefochtenen Urteilspunkte werden - unter dem Vorbehalt von <ref-law> - rechtskräftig (vgl. <ref-law>; Botschaft vom 21. Dezember 2005 zur Vereinheitlichung des Strafprozessrechts, BBl 2006 1315 Ziff. 2.9.3.1; Urteil 6B_533/2016 vom 29. November 2016 E. 4.2 mit Hinweisen; SCHMID/JOSITSCH, Schweizerische Strafprozessordnung, Praxiskommentar, 3. Aufl. 2018, N. 1 zu <ref-law>; LUZIUS EUGSTER, a.a.O., N. 2 zu <ref-law>, N. 1 und 3 zu <ref-law>; MARLÈNE KISTLER VIANIN, in: Commentaire romand, Code de procédure pénale suisse, 2011, N. 3 zu <ref-law>; HUG/SCHEIDEGGER, in: Kommentar zur Schweizerischen Strafprozessordnung, Donatsch/ Hansjakob/Lieber [Hrsg.], 2. Aufl. 2014, N. 14 zu <ref-law>; NIKLAUS OBERHOLZER, Grundzüge des Strafprozessrechts, 3. Aufl. 2012, Rz. 1615; offengelassen bei THOMAS SPRENGER, in: Basler Kommentar, Schweizerische Strafprozessordnung, 2. Aufl. 2014, N. 31 zu <ref-law>). Eine spätere Ausdehnung der Berufung ist ausgeschlossen, nicht aber eine weitere Beschränkung (Urteil 6B_1160/2017 vom 17. April 2018 E. 1.1 mit Hinweisen; BBl 2006 1314 Ziff. 2.9.3.1; SCHMID/JOSITSCH, a.a.O., N. 16 zu <ref-law>; MOREILLON/PAREIN-REYMOND, Petit commentaire, Code de procédure pénale, 2. Aufl. 2016, N. 33 zu <ref-law>; LUZIUS EUGSTER, a.a.O., N. 6 zu <ref-law>; NIKLAUS OBERHOLZER, a.a.O., Rz. 1615; MARLÈNE KISTLER VIANIN, a.a.O., N. 21 zu <ref-law>).
Von der Möglichkeit des Eingriffs in die Dispositionsfreiheit der beschuldigten Person ist nur zurückhaltend Gebrauch zu machen. Der Eingriff in die Dispositionsmaxime ist in sachlicher Hinsicht auf die Verhinderung von gesetzeswidrigen oder unbilligen Entscheidungen beschränkt. Eine umfassende, freie Überprüfung (blosse Unangemessenheit) ist damit ausgeschlossen. Es soll verhindert werden, dass das Berufungsgericht auf einer materiell unrichtigen Grundlage urteilen muss. <ref-law> kommt vorwiegend bei einer qualifiziert unrichtigen Rechtsanwendung durch die Vorinstanz bei gleichzeitiger Beschränkung der Berufung auf die Sanktion zur Anwendung. Beschränkt etwa der Beschuldigte die Berufung auf den Strafpunkt, kann es dem Gericht nicht verwehrt sein, auch den Schuldpunkt neu zu beurteilen und den Beschuldigten nicht nur milder zu bestrafen, sondern das Verfahren einzustellen oder ihn statt wegen schwerer bloss wegen einfacher Körperverletzung, oder statt wegen Raubes, "nur" wegen Diebstahls schuldig zu sprechen. Gesetzwidrig wäre eine Entscheidung auch dann, wenn das erstinstanzliche Gericht eine unzulässige Sanktion ausgesprochen hätte. In Ermessensentscheide der Vorinstanz kann hingegen in keinem Fall eingegriffen werden; eine Beschränkung der Dispositionsmaxime rechtfertigt sich nur bei Willkür (vgl. Urteile 6B_1160/2017 vom 17. April 2018 E. 1.5; 6B_769/2016 vom 11. Januar 2017 E. 2.3; 6B_349/2016 vom 13. Dezember 2016 E. 2.3; 6B_634/2012 vom 11. April 2013 E. 2.3.1; je mit Hinweisen; LUZIUS EUGSTER, a.a.O., N. 4 f. zu <ref-law>; MARLÈNE KISTLER VIANIN, a.a.O., N. 2 ff. zu <ref-law>). Macht das Berufungsgericht von <ref-law> Gebrauch, hat es die Verfahrensbeteiligten vorher zu informieren und ihnen Gelegenheit zur Stellungnahme zu geben (Urteile 6B_769/2016 vom 11. Januar 2017 E. 2.3; 6B_349/2016 vom 13. Dezember 2016 E. 2.3; 6B_634/2012 vom 11. April 2013 E. 2.3.1; je mit Hinweisen).
2.4.
2.4.1. Gemäss den vorinstanzlichen Feststellungen hat die frühere amtliche Verteidigerin des Beschwerdeführers die Berufung eindeutig auf die Strafzumessung beschränkt. In der schriftlichen Berufungsbegründung führte sie wörtlich aus: "Der Berufungskläger akzeptiert den Schuldspruch wegen Mordes gemäss <ref-law>. Die Tatausführung war grausam." Vor Bundesgericht macht der Beschwerdeführer denn auch nicht mehr geltend, es sei unklar, welche Punkte die Berufung umfasst habe. Demnach ist die Einschränkung der Berufung auf die Bemessung der Strafe eindeutig.
2.4.2. Zu prüfen ist, ob diese Beschränkung angesichts der konkreten Umstände und in Nachachtung des Grundsatzes der Untrennbarkeit zulässig war. In der Berufungsbegründung vom 10. Februar 2017 akzeptierte die damalige amtliche Verteidigerin des Beschwerdeführers wie gesagt zwar explizit den Schuldspruch wegen Mordes. Allerdings wendete sie sich gegen die Annahme des erstinstanzlichen Gerichts, dass eine sexuelle Frustration des Beschwerdeführers beziehungsweise ein Streit über die Qualität und den Umfang der sexuellen Dienstleistungen Motiv für die Tat gewesen seien. Sie machte geltend, dass erhebliche Zweifel an den entsprechenden Sachverhaltsfeststellungen des erstinstanzlichen Gerichts bestünden. Ferner führte sie aus, der Beschwerdeführer sei sich während des Zustechens der Grausamkeit seiner Tatausführung nicht bewusst gewesen. Er habe sich aufgrund der Anwesenheit einer Drittperson, die sich im Schrank versteckt habe, in einem Zustand höchster Panik und Angst befunden. Weiter argumentierte sie, der Beschwerdeführer habe während der Tat unter dem Einfluss von unreinem Kokain gestanden, dessen Wirkung er als radikal und heftig bezeichnet habe. Dies habe die Angst und Panik während der Tat verstärkt und sein Bewusstsein geschmälert. Dass seine Panik und die entsprechende Reaktion übermässig gewesen seien, müsse im Wesentlichen der Wirkung des unreinen Kokains zugeschrieben werden und widerspreche seinem gewohnten Verhalten. Er habe das Opfer nicht bewusst besonders grausam getötet. Entsprechend sei auch bezüglich der besonderen Grausamkeit innerhalb des Mordtatbestands kein schweres Verschulden gegeben (kantonale Akten, act. 2111 ff.).
Mit diesen Ausführungen wandte sich die damalige amtliche Verteidigerin des Beschwerdeführers gegen die tatsächlichen Feststellungen der ersten Instanz. Sowohl der Schuldspruch wegen Mordes als auch die Strafzumessung beziehungsweise die Bewertung des Verschuldens durch die erste Instanz basieren auf diesen tatsächlichen Feststellungen. Indem sich die Berufung offensichtlich gegen die tatsächlichen Grundlagen des Schuldpunkts einerseits und der Bemessung der Strafe andererseits richtete, bestand zwischen diesen beiden Punkten ein innerer Zusammenhang, weshalb sie nicht losgelöst voneinander beurteilt werden konnten. Folglich war im vorliegenden Fall angesichts der konkret vorgebrachten Rügen eine Beschränkung der Berufung auf die Bemessung der Strafe nicht möglich, was der Vorinstanz hätte auffallen müssen. Dieser Umstand führt jedoch aus nachfolgenden Gründen nicht zur Gutheissung der Beschwerde.
2.4.3. Aus dem vorinstanzlichen Urteil ergibt sich, dass die Vorinstanz zwar formell davon ausging, die Berufung beschränke sich auf die Bemessung der Strafe, sie jedoch faktisch den Sachverhalt, welcher der rechtlichen Würdigung und der Strafzumessung zu Grunde liegt, selbst feststellt, indem sie sich mit der vom Beschwerdeführer vorgebrachten Kritik an den tatsächlichen Feststellungen der ersten Instanz im Rahmen der Strafzumessung ausführlich auseinandersetzt. Sie geht detailliert auf seine Vorbringen im Zusammenhang mit seinem Motiv für die Tat ein, verwirft seinen Einwand, es habe sich um eine Notwehrsituation gehandelt, und gelangt zum Schluss, das Tatmotiv sei im Zusammenhang mit der sexuellen Dienstleistung, die das Opfer erbracht beziehungsweise nicht erbracht haben solle, zu werten. Ob dabei die sexuelle Frustration des Beschwerdeführers oder Meinungsverschiedenheiten über die Bezahlung der bezogenen Liebesdienste den Ausschlag für die Tötung des Opfers gegeben hätten, spiele letztlich keine Rolle; in jedem Fall stehe das Motiv in krassem Missverhältnis zum Wert eines Menschenlebens. In der Folge geht die Vorinstanz im Rahmen der Prüfung einer allenfalls verminderten Schuldfähigkeit auf den Einwand des Beschwerdeführers ein, die Tatsache, dass er derart ausgerastet sei, lasse sich nur mit dem Konsum von Betäubungsmitteln erklären. Sie gelangt zum Schluss, dass insbesondere angesichts des äusserst zielgerichteten Nachtatverhaltens für die Variante eines Konsums von das Bewusstsein verändernden Substanzen kein Platz sei. Sie ergänzt, der Beschwerdeführer habe anlässlich der Berufungsverhandlung wie auch im Strafvollzug gezeigt, dass er auch ohne Einnahme von Betäubungsmitteln und aus nichtigem Anlass ausserordentlich aggressiv reagieren könne. Das Verhalten des Beschwerdeführers erscheine persönlichkeitsadäquat und lasse gerade nicht darauf schliessen, dass er zum Zeitpunkt der Tat unter bewusstseinsverändernden Betäubungsmitteln gestanden sei. Damit setzt sich die Vorinstanz mit allen tatsächlichen Vorbringen des Beschwerdeführers auseinander (Urteil S. 13 ff.).
In rechtlicher Hinsicht ergibt sich aus dem vorinstanzlichen Urteil, dass auch die Vorinstanz das Verhalten des Beschwerdeführers als Mord im Sinne von <ref-law> qualifiziert. Zwar nimmt sie aufgrund der von ihr angenommenen Beschränkung der Berufung keine eigentliche rechtliche Qualifikation des erstellten Sachverhalts vor, führt jedoch mehrfach aus, dass das Verhalten des Beschwerdeführers besonders grausam und skrupellos im Sinne von <ref-law> gewesen sei. Dies ergibt sich einerseits aus ihren Erwägungen zu <ref-law>, worin sie erwägt, das erstinstanzliche Urteil sei weder unbillig noch gesetzeswidrig, da nicht zu beanstanden sei, dass die erste Instanz die Tat des Beschwerdeführers in objektiver und subjektiver Hinsicht als Mord qualifiziere (Urteil S. 7). Andererseits führt die Vorinstanz im Rahmen der Bemessung des objektiven Tatverschuldens unter anderem aus, die erste Instanz sei zu Recht davon ausgegangen, dass sich das skrupellose Handeln des Beschwerdeführers vorliegend bereits aus der grausamen Tatausführung erschliesse und somit die Mordqualifikation primär auf der Art der Ausführung beruhe. Die Vorinstanz setzt sich mit den Vorbringen des Beschwerdeführers auseinander, weshalb nicht von einem skrupellosen und grausamen Vorgehen auszugehen sei, und verwirft diese. Mit der ersten Instanz nimmt sie an, da keiner der 37 Stiche für sich alleine tödlich gewesen sei, sei der Todeskampf des Opfers besonders grausam gewesen und dieses habe einen nicht nachvollziehbaren langen Leidensweg gehen müssen (Urteil S. 12 f.).
Aus dem Gesagten ergibt sich, dass die Vorinstanz faktisch sowohl den Schuldspruch als auch die Bemessung der Strafe überprüft beziehungsweise selbst vornimmt. Folglich erlitt der Beschwerdeführer durch die formelle Beschränkung des Berufungsverfahrens auf die Frage der Bemessung der Strafe keinen Nachteil. Es erübrigt sich daher auch, auf seinen Einwand, die Urteilsbegründung des erstinstanzlichen Gerichts sei mangelhaft, näher einzugehen. Jedoch ist nachfolgend die Kritik des Beschwerdeführers an der vorinstanzlichen Sachverhaltsfeststellung und an der rechtlichen Qualifikation seiner Tat als Mord zu prüfen.
2.5.
2.5.1. Mit seinen Ausführungen legt der Beschwerdeführer nicht dar, dass die tatsächlichen Feststellungen und/oder die rechtlichen Erwägungen der Vorinstanz Bundesrecht verletzen. In tatsächlicher Hinsicht argumentiert er, er sei vor der Tatbegehung aus nicht restlos nachvollziehbaren Gründen in Panik geraten und der Griff zum Messer sei eine spontane Reaktion gewesen. Die Vorinstanz hätte den Zeugen B._, dessen Angaben sie bei der Qualifikation des Verhaltens des Beschwerdeführers als Mord entscheidendes Gewicht zumesse, nochmals anhören müssen. Da sie dies nicht getan habe, seien dessen Aussagen nicht verwertbar.
2.5.2. Das Rechtsmittelverfahren beruht auf den Beweisen, die im Vorverfahren und im erstinstanzlichen Hauptverfahren erhoben worden sind (<ref-law>). Dieser Grundsatz gelangt indes nur zur Anwendung, soweit die Beweise, auf welche die Rechtsmittelinstanz ihren Entscheid stützen will, prozessrechtskonform erhoben worden sind. Erweisen sich die Beweiserhebungen des erstinstanzlichen Gerichts als rechtsfehlerhaft (lit. a), unvollständig (lit. b) oder erscheinen sie als unzuverlässig (lit. c), werden sie von der Rechtsmittelinstanz wiederholt (<ref-law>). Sofern die unmittelbare Kenntnis des Beweismittels für die Urteilsfällung notwendig erscheint, erhebt das Berufungsgericht zudem auch im Vorverfahren ordnungsgemäss erhobene Beweise noch einmal (Art. 343 Abs. 3 i.V.m. <ref-law>; <ref-ruling> E. 1.4.1 S. 290 f.; Urteile 6B_1469/2017 vom 18. Juni 2018 E. 1.3; 6B_886/2017 vom 26. März 2018 E. 1.3.1; je mit Hinweisen). Eine unmittelbare Abnahme eines Beweismittels ist namentlich notwendig, wenn es den Ausgang des Verfahrens beeinflussen kann, insbesondere wenn die Kraft des Beweismittels in entscheidender Weise vom Eindruck abhängt, der bei seiner Präsentation entsteht. Dies ist etwa der Fall, wenn es in besonderem Masse auf den unmittelbaren Eindruck einer Zeugenaussage ankommt, so wenn die Aussage das einzige direkte Beweismittel (Aussage gegen Aussage-Konstellation) darstellt (<ref-ruling> E. 4.4.2 S. 199 f.; Urteile 6B_1469/2017 vom 18. Juni 2018 E. 1.3; 6B_886/2017 vom 26. März 2018 E. 1.3.1; 6B_800/2016 vom 25. Oktober 2017 E. 9.2, nicht publ. in: <ref-ruling>; 6B_888/2017 vom 25. Oktober 2017 E. 3.3, nicht publ. in: <ref-ruling>; je mit Hinweisen).
Der Beschwerdeführer begründet nicht, weshalb die Einvernahme von B._ bei der Staatsanwaltschaft nicht verwertbar sein sollte. Insbesondere macht er nicht geltend, dass er beziehungsweise seine Verteidigung daran nicht habe teilnehmen können oder dass er keine Gelegenheit zur Stellung von Ergänzungsfragen erhalten habe (vgl. <ref-law>; Urteil S. 9). Selbst wenn die Vorinstanz gestützt auf Art. 343 Abs. 3 i.V.m. <ref-law> verpflichtet gewesen wäre, den Zeugen selbst nochmals zu befragen, hätte dies nicht zur Folge, dass dessen frühere Einvernahme nicht verwertbar wäre. Vielmehr läge eine Verletzung der genannten Bestimmungen und des Anspruchs auf rechtliches Gehör des Beschwerdeführers vor. Dies ist jedoch aufgrund der vorliegenden Konstellation nicht der Fall, da die Vorinstanz wie auch die erste Instanz die Aussagen von B._ bei der Prüfung des Tatmotivs lediglich als ergänzendes Indiz heranziehen. Daneben berücksichtigen sie weitere Umstände, wie die Aussage der Vermittlerin der Liebesdienste, das bedrohliche und aggressive Verhalten des Beschwerdeführers im vorzeitigen Strafvollzug sowie an der Berufungsverhandlung und Berichte des IRM sowie der KTA (Urteil S. 13 ff.; erstinstanzliches Urteil S. 10 ff.). Demnach liegt kein Fall von Art. 343 Abs. 3 i.V.m. <ref-law> vor und die Vorinstanz war nicht verpflichtet, den Zeugen persönlich zu befragen. Dem Umstand, dass der Beschwerdeführer und der Zeuge miteinander verfeindet waren, trägt die Vorinstanz im Rahmen der Beweiswürdigung Rechnung (Urteil S. 9, 14 f.). Wie sie zutreffend festhält, führt dies entgegen der Ansicht des Beschwerdeführers nicht dazu, dass auf die Aussage des Zeugen per se nicht abgestellt werden könnte.
Insgesamt legt der Beschwerdeführer nicht dar, dass die Sachverhaltsfeststellung der Vorinstanz offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (vgl. <ref-law>; <ref-ruling> E. 2.3.1 S. 244; <ref-ruling> E. 2.2 S. 313; je mit Hinweis) oder den Grundsatz "in dubio pro reo" verletzt.
2.5.3. Schliesslich verletzt die Vorinstanz auch kein Bundesrecht, indem sie das Verhalten des Beschwerdeführers zumindest implizit als Mord qualifiziert beziehungsweise den entsprechenden erstinstanzlichen Schuldspruch als zutreffend bezeichnet.
Eine vorsätzliche Tötung ist als Mord zu qualifizieren, wenn der Täter besonders skrupellos handelt, namentlich wenn sein Beweggrund, der Zweck der Tat oder die Art der Ausführung besonders verwerflich sind (<ref-law>). Mord zeichnet sich nach der Rechtsprechung durch eine aussergewöhnlich krasse Missachtung fremden Lebens bei der Durchsetzung eigener Absichten aus. Es geht um die besonders verwerfliche Auslöschung eines Menschenlebens. Für die Qualifikation verweist das Gesetz in nicht abschliessender Aufzählung auf äussere (Ausführung) und innere Merkmale (Beweggrund, Zweck). Diese müssen nicht alle erfüllt sein, um Mord anzunehmen. Entscheidend ist eine Gesamtwürdigung der äusseren und inneren Umstände der Tat. Eine besondere Skrupellosigkeit kann beispielsweise entfallen, wenn das Tatmotiv einfühlbar und nicht krass egoistisch war, so etwa wenn die Tat durch eine schwere Konfliktsituation ausgelöst wurde. Für Mord typische Fälle sind die Tötung eines Menschen zum Zwecke des Raubes, Tötungen aus religiösem oder politischem Fanatismus oder aus Geringschätzung. Die für eine Mordqualifikation konstitutiven Elemente sind jene der Tat selber, während Vorleben und Verhalten nach der Tat nur heranzuziehen sind, soweit sie tatbezogen sind (<ref-ruling> E. 4.1 S. 64 f.; <ref-ruling> E. 1a S. 13 f.; Urteile 6B_28/2017 vom 23. Januar 2018 E. 2.3; 6B_480/2016 vom 5. August 2016 E. 1.3.2; je mit Hinweisen).
Angesichts der vorinstanzlichen Sachverhaltsfeststellungen ist es nicht zu beanstanden, wenn die Vorinstanz mit der ersten Instanz die Tatausführung als besonders grausam bezeichnet. Der Beschwerdeführer hat insgesamt 37 Mal auf das Opfer eingestochen, wobei es zu fünf vollständigen Durchstichen kam, was gemäss Vorinstanz eine grosse Wucht beziehungsweise enorme Kraft voraussetzt. Dem Argument der Verteidigung, wonach unzählige wahllose Messerstiche gegen ein besonders geplantes respektive skrupelloses Verhalten, sondern vielmehr dafür sprächen, dass sich der Täter in einer emotionalen Schieflage befunden habe, kann nicht gefolgt werden. Gemäss den tatsächlichen Feststellungen war keiner der Stiche für sich alleine tödlich, was zu einem langen Todeskampf des Opfers führte. Dies zeigt die besondere Grausamkeit des Vorgehens des Beschwerdeführers auf. Indem der Beschwerdeführer das Opfer ziellos brutal niederstach und dieses dadurch unnötig leiden liess, handelte er besonders skrupellos. Sein krass egoistischer Beweggrund, der gemäss den verbindlichen vorinstanzlichen Feststellungen im Zusammenhang mit der sexuellen Dienstleistung des Opfers zu orten ist, vermag die besondere Skrupellosigkeit selbstredend nicht entfallen zu lassen. Angesichts der gesamten äusseren und inneren Umstände verletzt der Schuldspruch wegen Mordes kein Bundesrecht.
3.
Da der Beschwerdeführer für den Fall der Abweisung seiner Beschwerde im Hauptpunkt keine Anträge zur Strafzumessung stellt beziehungsweise die vorinstanzliche Bemessung der Strafe nicht kritisiert, ist darauf nicht einzugehen.
4.
Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Der Beschwerdeführer wird grundsätzlich kostenpflichtig (<ref-law>). Sein Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist gutzuheissen, da von seiner Bedürftigkeit auszugehen ist und seine Rechtsbegehren nicht von vornherein aussichtslos waren. Es sind keine Kosten zu erheben. Seinem Rechtsvertreter ist eine Entschädigung aus der Bundesgerichtskasse auszurichten (Art. 64 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen.
3.
Es werden keine Kosten erhoben.
4.
Dem Rechtsvertreter des Beschwerdeführers, Advokat Dr. Nicolas Roulet, wird eine Entschädigung von Fr. 3'000.-- aus der Bundesgerichtskasse ausgerichtet.
5.
Dieses Urteil wird den Parteien, den Privatklägern und dem Appellationsgericht des Kantons Basel-Stadt, Kammer, schriftlich mitgeteilt.
Lausanne, 13. November 2018
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Andres