Sachverhalt:
A.
A.a. Das 2. Schwurgericht von Gaziantep in der Türkei verurteilte A._ mit Urteil vom 2. Mai 1989 zu einer lebenslänglichen Freiheitsstrafe. Der türkische Staatsangehörige kurdischer Ethnie war schuldig befunden worden, am 9. November 1988 aus Blutrache B._ erschossen zu haben. A._ habe sich mit dieser Tat für die Tötung seines Vaters durch den Sohn B._s gerächt. Das Urteil wurde von der Strafkammer des türkischen Kassationsgerichts mit Beschluss vom 23. Oktober 1989 bestätigt und ist rechtskräftig.
Mit Note vom 5. Oktober 2011 wurde der Schweiz ein Auslieferungsersuchen der Oberstaatsanwaltschaft Gaziantep vom 15. August 2011 übermittelt.
Das mit dem Gesuch befasste Bundesamt für Justiz (BJ) stellte daraufhin fest, dass A._ 1992 in der Schweiz ein Asylgesuch gestellt hatte. Zur Begründung hatte er damals vorgebracht, er habe als Sympathisant die PKK unterstützt und sei deshalb mehrmals kurzzeitig festgenommen, verhört und misshandelt worden. Im November 1988 seien er und seine beiden Brüder festgenommen und beschuldigt worden, B._ im Rahmen einer Blutfehde getötet zu haben. Trotz seiner Unschuld sei er zu einer lebenslänglichen Gefängnisstrafe verurteilt worden. Mit Hilfe seines Zwillingsbruders C._, mit dem er bei einem Gefängnisbesuch die Rollen getauscht habe, sei ihm im Sommer 1990 jedoch die Flucht gelungen. Er habe sich in der Folge versteckt und sei am 14. August 1992 ins Ausland gereist.
Mit Verfügung vom 26. August 1994 lehnte das damalige Bundesamt für Flüchtlinge (BFF, später Bundesamt für Migration [BFM], heute Staatssekretariat für Migration [SEM]) das Asylgesuch ab und ordnete den Vollzug der Wegweisung an. Die von A._ in der Folge eingereichte Beschwerde an die Schweizerische Asylrekurskommission (ARK, heute Bundesverwaltungsgericht) und zwei Revisionsgesuche blieben erfolglos. Indessen hiess das BFF am 17. September 1996 ein Wiedererwägungsgesuch teilweise gut. Es verweigerte zwar die Feststellung der Flüchtlingseigenschaft, da ein Ausschlussgrund nach Art. 1 (F) lit. b des Abkommens vom 28. Juli 1951 über die Rechtsstellung der Flüchtlinge (SR 0.142.30; im Folgenden: Flüchtlingskonvention, FK) bestehe. Hingegen ging es davon aus, dass A._ bei einer Rückkehr in die Türkei mit beachtlicher Wahrscheinlichkeit mit einer Verletzung seiner Rechte nach Art. 3 EMRK rechnen müsse und ordnete die vorläufige Aufnahme an. Eine hiergegen erhobene Beschwerde wies die ARK mit Urteil vom 19. September 2002 ab. Am 8. Februar 2010 erteilte das BFM A._ eine Aufenthaltsbewilligung wegen Vorliegen eines schwerwiegenden persönlichen Härtefalls gemäss Art. 84 Abs. 5 i.V.m Art. 30 Abs. 1 lit. b AuG (SR 142.20). Gleichzeitig stellte es das Erlöschen der vorläufigen Aufnahme fest.
A.b. Gestützt auf das Auslieferungsgesuch erliess das BJ am 7. Juni 2012 einen Auslieferungshaftbefehl. Am 21. Juni 2012 wurde A._ in Dübendorf festgenommen, eine Woche später jedoch gegen eine Kaution von Fr. 100'000.-- und unter Anordnung einer Schriftensperre und einer Meldepflicht vom BJ wieder entlassen.
A._ nahm in verschiedenen Schreiben Stellung zum Auslieferungsgesuch und erhob dabei die Einrede des politischen Delikts.
Mit Note vom 12. Juli 2012 ersuchte das BJ die türkische Botschaft in Bern um verschiedene Ergänzungen. Es wollte wissen, seit wann die türkischen Behörden über den Aufenthalt von A._ in der Schweiz informiert waren und aus welchen Gründen die Auslieferung nicht schon früher beantragt worden war. Weiter wurde um Stellungnahme zur Erklärung von A._ gebeten, wonach seine Verurteilung einzig auf einer später widerrufenen Aussage seines jüngsten Bruders, H._, beruhe, welche unter Folter zustande gekommen sei. Sodann wurde um Mitteilung gebeten, gestützt auf welche Beweismittel A._ von den türkischen Gerichten schuldig gesprochen worden war. Zudem ersuchte das BJ um Abgabe von folgenden Garantien in ausdrücklicher und wortgetreuer Form:
"a) Die Haftbedingungen des Verfolgten werden nicht unmenschlich bzw. erniedrigend sein und entsprechen den Anforderungen von Art. 3 EMRK.
b) Die physische und psychische Integrität des Verfolgten wird gewahrt werden (Art. 3 EMRK und Art. 7, 10 und 17 UNO-Pakt II).
c) Die Haftbedingungen des Verfolgten werden während des Strafvollzugs nicht wegen seiner politischen Anschauungen und Aktivitäten, wegen seiner Zugehörigkeit zu einer bestimmten sozialen Gruppe oder aus Gründen der Rasse, Religion oder Volkszugehörigkeit erschwert werden.
d) Dem gesundheitlichen Zustand des Verfolgten während der Haft wird in gebührendem Masse Rechnung getragen, namentlich durch eine angemessene medizinische Betreuung.
e) Die Behörden der türkischen Republik gewähren dem Verfolgten während der gesamten Dauer des Gefängnisaufenthalts einen uneingeschränkten und unbeaufsichtigten Kontakt bzw. Zugang zu seinem gewählten Rechtsanwalt bzw. zu seinem Pflichtverteidiger. Zudem hat der Verfolgte die Möglichkeit, im Gefängnis Besuche aus seinem Familien- bzw. Bekanntenkreis zu erhalten.
f) Der Schweizerischen Botschaft in Ankara wird das Recht zugesichert, Vertreter zu bezeichnen, die den Verfolgten nach dessen Auslieferung ohne Überwachungsmassnahmen jederzeit besuchen können. Der Verfolgte hat jederzeit das Recht, sich an diese Vertreter zu wenden."
Mit Schreiben vom 30. August 2012 erteilte die Oberstaatsanwaltschaft Gaziantep die vom BJ verlangten Auskünfte. Mit Note vom 10. September 2012 wurde der Schweiz zudem eine die angeforderten Garantien betreffende Erklärung des türkischen Justizministeriums übermittelt.
A.c. Am 2. August 2012 reichte A._ beim BFM ein neues Asylgesuch ein. Dieses begründete er im Wesentlichen mit seinen exilpolitischen Aktivitäten. Danach hat er als Chauffeur für hochrangige PKK-Funktionäre fungiert. Er soll dabei den Bruder des PKK-Führers D._ nach Belgien zu TV E._ gefahren haben. Ebenso soll er in Deutschland einen hochrangigen PKK-Funktionär, welcher dort unter Hausarrest gestanden sei, besucht haben. Daneben habe er mit seiner Ehefrau zusammen bei verschiedenen Anlässen Tee und Kaffee verkauft und für das kurdische Hilfswerk I._ Spenden gesammelt. A._ gab sich in seinem Gesuch überzeugt, dass der türkische Geheimdienst über seine umfangreichen exilpolitischen Tätigkeiten informiert sei. Die Militärs würden seinen in der Türkei lebenden Bruder immer wieder nach ihm fragen. Auch würden seine Angehörigen bei der Wiedereinreise in die Türkei am Flughafen von den dortigen Sicherheitskräften nach ihm gefragt. Er brachte vor, dass das erst nach seinem langjährigen Aufenthalt in der Schweiz von den türkischen Behörden gestellte Auslieferungsersuchen wohl auf seine exilpolitischen Aktivitäten zurückzuführen sei.
A.d. Das BJ wies die türkische Botschaft mit Note vom 14. Januar 2013 darauf hin, dass die angeforderten Garantien nicht in ausdrücklicher und wortgetreuer Form abgegeben worden seien. Die türkischen Behörden übermittelten darauf noch zwei weitere Male unzureichende Garantien. Die vierte Erklärung, datierend vom 22. März 2013, entsprach schliesslich dem Geforderten.
A.e. Mit Asylentscheid vom 29. Januar 2014 stellte das BFM fest, es sei davon auszugehen, dass die Vorbringen von A._ geeignet seien, materiell die Flüchtlingseigenschaft zu begründen. Die massgebliche Sachlage habe sich seit der Verfügung des BFF vom 17. September 1996 und dem Urteil der ARK vom 28. (recte: 19.) September 2002 nicht geändert. A._ könne jedoch nicht als Flüchtling anerkannt werden, weil er in Anwendung von Art. 1 (F) lit. b FK von der Flüchtlingseigenschaft ausgeschlossen werde. Sein Asylgesuch sei deshalb abzulehnen. A._ sei damit grundsätzlich zur Ausreise verpflichtet. Aus den Akten würden sich jedoch konkrete Anhaltspunkte dafür ergeben, dass ihm im Falle einer Rückkehr in den Heimatstaat mit beachtlicher Wahrscheinlichkeit eine durch Art. 3 EMRK verbotene Strafe oder Behandlung drohe. Der Vollzug der Wegweisung in den Herkunfts- bzw. den Heimatstaat sei deshalb im gegenwärtigen Zeitpunkt nicht zulässig. A._ sei nach dem Eintritt der Rechtskraft des Asylentscheides in der Schweiz vorläufig aufzunehmen.
Mit Verfügung vom 19. Februar 2014 korrigierte das BFM seinen Asylentscheid vom 29. Januar 2014. Es sei einem Irrtum erlegen. Da A._ bereits über eine Aufenthaltsbewilligung B in der Schweiz verfüge, sei eine Wegweisung im Rahmen des Asylverfahrens von vornherein ausgeschlossen. Der Entscheid über die Wegweisung falle in die Zuständigkeit der kantonalen Migrationsbehörden. Das BFM beschränkte sich deshalb darauf, erstens festzustellen, dass A._ die Flüchtlingseigenschaft nicht erfülle, zweitens das Asylgesuch abzulehnen und drittens davon Vormerk zu nehmen, dass A._ über eine Aufenthaltsbewilligung B verfüge. Dieser korrigierte Asylentscheid blieb unangefochten.
A.f. Mit Auslieferungsentscheid vom 18. Juli 2014 bewilligte das BJ die Auslieferung von A._ an die Türkei für die dem Auslieferungsersuchen zugrunde liegenden Straftaten. Der Auslieferungsentscheid erfolge unter Vorbehalt des Entscheids des Bundesstrafgerichts über die Einrede des politischen Delikts im Sinne von <ref-law> (SR 351.1). Die Haftkaution in der Höhe von Fr. 100'000.-- werde gestützt auf <ref-law> zur Deckung der Kosten des Auslieferungsverfahrens verwendet, ein allfälliger Überschuss zurückerstattet.
Mit Eingabe vom 6. August 2014 erhob A._ Beschwerde beim Bundesstrafgericht. Er beantragte insbesondere, der Auslieferungsentscheid des BJ sei aufzuheben und das Auslieferungsgesuch abzulehnen. Im Rahmen des Schriftenwechsels reichte er einen Arztbericht von Dr. med. F._ vom 19. August 2014 ein, wonach eine Auslieferung sowohl aus körperlicher wie auch psychischer Sicht kontraindiziert wäre und wonach A._ aus psychischer Sicht "absolut nicht hafttauglich" sei.
Mit Entscheid vom 7. Mai 2015 vereinte das Bundesstrafgericht das Verfahren betreffend die Einrede des politischen Delikts und das Beschwerdeverfahren (Dispositiv-Ziffer 1) und wies sowohl die Einrede (Dispositiv-Ziffer 2) als auch die Beschwerde (Dispositiv-Ziffer 3) ab.
B.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht vom 22. Mai 2015 beantragt A._ im Wesentlichen, der Entscheid des Bundesstrafgerichts sei aufzuheben, die Einrede des politischen Delikts gutzuheissen und der Auslieferungsentscheid des BJ aufzuheben. Zudem sei festzustellen, dass die Auslieferung zwingenden völkerrechtlichen Bestimmungen widerspreche und unzulässig sei. Weiter sei das BJ anzuweisen, ihm eine Entschädigung für die Haft und eine Genugtuung zuzusprechen.
Das Bundesstrafgericht verweist in seiner Vernehmlassung auf den angefochtenen Entscheid. Das BJ beantragt, auf die Beschwerde nicht einzutreten, weil kein besonders bedeutender Fall gemäss <ref-law> vorliege. Zum Verfahren im Nachgang des Entscheids des Bundesstrafgerichts hält das BJ fest, es habe am 13. Mai 2015 einen Auslieferungshaftbefehl erlassen. Am 15. Mai 2015 sei A._ festgenommen und zwecks Abklärung seines Gesundheitszustands in die Psychiatrische Klinik G._ eingewiesen worden. Gegen den Auslieferungshaftbefehl habe er Beschwerde beim Bundesstrafgericht erhoben. Aus dem angeforderten amtsärztlichen Bericht vom 22. Mai 2015 ergebe sich, dass A._ grundsätzlich hafterstehungs- und transportfähig sei. Falls vom Beschwerdeführer gewünscht, werde das BJ im Falle einer Auslieferung den türkischen Behörden ein aktuelles Arztzeugnis einreichen und diese namentlich auf eine mögliche Suizidgefahr und die notwendige Medikation hinweisen.
In seiner Replik bringt der Beschwerdeführer vor, die Strafe sei nach türkischem Recht verjährt, da ein Amnestiegesetz erlassen worden sei. Dieses gelte aufgrund eines Entscheids des türkischen Verfassungsgerichts auch im vorliegenden Fall. Das BJ reicht in seiner Duplik ein Urteil des 2. Schwurgerichts von Gaziantep vom 22. Juni 2015 ein, wonach die Vollstreckungsverjährung nach türkischem Recht noch nicht eingetreten ist. Der Beschwerdeführer hat dazu Stellung genommen und hält an seiner Auffassung fest.

Erwägungen:
1.
1.1. Der angefochtene Entscheid des Bundesstrafgerichts betrifft das Gebiet der internationalen Rechtshilfe in Strafsachen. Dagegen ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegeben (Art. 82 lit. a, Art. 84 und Art. 86 Abs. 1 lit. b BGG).
1.2. Gemäss <ref-law> ist gegen einen Entscheid auf dem Gebiet der internationalen Rechtshilfe in Strafsachen die Beschwerde in öffentlich-rechtlichen Angelegenheiten nur zulässig, wenn er unter anderem eine Auslieferung betrifft und es sich um einen besonders bedeutenden Fall handelt (Abs. 1). Ein besonders bedeutender Fall liegt insbesondere vor, wenn Gründe für die Annahme bestehen, dass elementare Verfahrensgrundsätze verletzt worden sind oder das Verfahren im Ausland schwere Mängel aufweist (Abs. 2).
<ref-law> bezweckt die wirksame Begrenzung des Zugangs zum Bundesgericht im Bereich der internationalen Rechtshilfe in Strafsachen (<ref-ruling> E. 3 S. 132 mit Hinweis). Ein besonders bedeutender Fall kann deshalb auch bei einer Auslieferung nur ausnahmsweise angenommen werden. In der Regel stellen sich insoweit keine Rechtsfragen, die der Klärung durch das Bundesgericht bedürfen, und kommt den Fällen auch sonst wie keine besondere Tragweite zu (<ref-ruling> E. 1.3.4 S. 161). Bei der Beantwortung der Frage, ob ein besonders bedeutender Fall gegeben ist, steht dem Bundesgericht zudem ein weiter Ermessensspielraum zu (<ref-ruling> E. 1.3.1 S. 160 mit Hinweis).
1.3. Der Beschwerdeführer macht geltend, von der Türkei aus politischen Motiven verfolgt zu werden (Art. 3 des Europäischen Auslieferungsübereinkommens vom 13. Dezember 1957 [SR 0.353.1; im Folgenden: EAUe]). Eine Auslieferung widerspräche zudem Art. 3 EMRK. Die von der Türkei abgegebenen Garantien genügten nicht, um der Gefahr einer unmenschlichen Behandlung zu begegnen.
Die schweizerischen Asylbehörden sind in mehreren Entscheiden davon ausgegangen, dass dem Beschwerdeführer im Falle einer Rückkehr in seinen Heimatstaat mit beachtlicher Wahrscheinlichkeit eine nach Art. 3 EMRK verbotene Strafe oder Behandlung drohe. Da gleichzeitig ein Asylausschlussgrund bejaht wurde, wurde die vorläufige Aufnahme angeordnet. Das Bundesstrafgericht ist in Bezug auf die Einschätzung der Zumutbarkeit der Rückkehr bzw. der Auslieferung von dieser Beurteilung der Asylbehörden abgewichen. Dasselbe gilt für die vom Beschwerdeführer vorgelegten ärztlichen Berichte, wonach er an einer posttraumatischen Belastungsstörung leide, die zweifellos auf Foltererfahrungen in der Türkei zurückzuführen sei und die eine Auslieferung aus medizinischer Sicht als nicht verantwortbar erscheinen lasse.
Diese Hinweise auf eine Art. 3 EMRK widersprechende Behandlung sind hinreichend konkret und nicht ohne Weiteres von der Hand zu weisen. Es geht insoweit um Leib und Leben und damit um das höchste Rechtsgut. Es besteht deshalb Anlass zu einer inhaltlichen Auseinandersetzung mit den Vorbringen des Beschwerdeführers (vgl. <ref-ruling> E. 1.3.3 S. 160 f.). Hierfür spricht auch, dass aufgrund der gemäss dem Auslieferungsersuchen noch zu verbüssenden Restfreiheitsstrafe von über 34 Jahren der Entscheid über die Auslieferung für den Beschwerdeführer von erheblicher Tragweite ist (vgl. Urteil 1C_91/2007 vom 23. Oktober 2007 E. 1.3.3). Die Voraussetzung des besonders bedeutenden Falls ist somit erfüllt.
1.4. Der Beschwerdeführer hat vor der Vorinstanz am Verfahren teilgenommen. Er ist durch den angefochtenen Entscheid besonders berührt und hat ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung. Er ist deshalb nach <ref-law> zur Beschwerde befugt.
1.5. Die weiteren Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf die Beschwerde ist im Grundsatz einzutreten.
1.6. Nicht einzutreten ist auf die Beschwerde allerdings insoweit, als in der Beschwerde eine Liste von angeblich verletzten Rechtsbestimmungen aufgeführt, aber teilweise nicht näher dargelegt wird, weshalb diese durch den angefochtenen Entscheid verletzt worden sein sollen (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG).
2.
Für den Auslieferungsverkehr zwischen der Schweiz und der Türkei sind primär das EAUe und dessen zweites Zusatzprotokoll vom 17. März 1978 (SR 0.353.12) massgebend. Soweit darin bestimmte Fragen nicht abschliessend geregelt sind, findet auf das Verfahren der Auslieferung ausschliesslich das Recht des ersuchten Staates Anwendung (Art. 22 EAUe), vorliegend also das IRSG und die Verordnung vom 24. Februar 1982 über internationale Rechtshilfe in Strafsachen (Rechtshilfeverordnung, IRSV; SR 351.11). Das innerstaatliche Recht gelangt nach dem Günstigkeitsprinzip auch dann zur Anwendung, wenn dieses geringere Anforderungen an die Rechtshilfe stellt (<ref-ruling> E. 2.2.2 S. 40 f. mit Hinweis). Vorbehalten bleibt die Wahrung der Menschenrechte (<ref-ruling> E. 2.3 S. 215 mit Hinweis).
3.
3.1. Nach Massgabe des EAUe sind die Vertragsparteien grundsätzlich verpflichtet, einander Personen auszuliefern, die von den Justizbehörden des ersuchenden Staates wegen einer strafbaren Handlung verfolgt oder zur Vollstreckung einer Strafe oder einer sichernden Massnahme gesucht werden (Art. 1 EAUe). Wird die Auslieferung wie hier aufgrund einer Verurteilung zu einer Strafe im Hoheitsgebiet des ersuchenden Staats verlangt, so muss diese mindestens vier Monate betragen (Art. 2 Ziff. 1 EAUe).
3.2. Der Beschwerdeführer bestreitet nicht, dass eine auslieferungsfähige strafbare Handlung in Frage steht, auch wenn er bestreitet, diese begangen zu haben. Er ist jedoch der Ansicht, der Auslieferung stünden Ausschlussgründe entgegen.
4.
4.1. Der Beschwerdeführer bringt vor, er sei in der Türkei gestützt auf einen durch Folter erwirkten Beweis verurteilt worden, was die Auslieferung gemäss <ref-law> ausschliesse. Das Bundesstrafgericht stelle zu Unrecht erhöhte Anforderungen an das Glaubhaftmachen von Folter. Bereits in den Asylverfahren sei festgestellt worden, dass ihm bei einer Rückkehr in die Türkei Folter drohe. Das Bundesstrafgericht selbst gestehe ein, dass im Zeitraum, als er in der Türkei festgenommen worden sei, Folter im Polizeigewahrsam ein extrem weit verbreitetes Problem gewesen sei. Anerkannt werde auch, dass der Hauptbelastungszeuge, H._, ausgesagt habe, dass er die belastenden Aussagen gemacht habe, um sich vor den Schlägen der Polizisten zu retten. Dass die über Tage hinweg erlittene Folter keine Spuren hinterlassen habe, spreche keineswegs gegen die Glaubhaftigkeit seiner Schilderungen. Zudem sei notorisch, dass es schwierig sei, in der Türkei einen Arzt zu finden, der die Folterspuren schriftlich bestätige. Schliesslich lägen nun auch neuere fachärztliche Berichte vor, die eine Belastungsstörung diagnostizierten und diese auf die erlittene Folter zurückführten.
4.2. Das Bundesstrafgericht legt dar, der pauschale Hinweis des Beschwerdeführers auf notorische Berichte über Folter in türkischen Strafverfahren reiche nicht. Im türkischen Strafverfahren habe H._ zunächst die Verantwortung für die Tat übernommen, später dann aber den Beschwerdeführer belastet. Würde man seiner sich aus den Gerichtsunterlagen ergebenden Darstellung folgen, auf welche sich auch der Beschwerdeführer stütze, so wäre er sowohl nach seinem Geständnis als auch nach der Belastung seines Bruders weiter gefoltert worden, was keinen Sinn ergebe. Auch seien in den Arztberichten, auf welche im türkischen Strafurteil verwiesen worden sei, keine Spuren von Folterhandlungen bei den drei Angeklagten festgestellt worden. Hierzu habe sich der Beschwerdeführer sowohl in den beiden Asylverfahren als auch im Auslieferungsverfahren nicht geäussert. Dabei habe er im Asylverfahren unter anderem ausgesagt, er sei unter den Füssen mit etwas Hartem geschlagen worden und seine Füsse würden noch Spuren davon tragen. Er sei ausserdem hinter seinen Ohren geschlagen worden und sein rechtes Ohr habe stark zu bluten begonnen. Die Nähnarben seien noch zu sehen. Ausserdem habe man ihm am ganzen Körper Elektroschocks verabreicht. Sein rechtes Handgelenk sei dabei verletzt worden, als er bei gefesseltem Handgelenk stark zusammengezuckt sei. Er trage davon noch Spuren. Weshalb der durch mehrere Rechtsvertreter verteidigte Beschwerdeführer im türkischen Strafverfahren die geltend gemachten Folterungen nicht ärztlich habe bestätigen lassen, leuchte nicht ein und erwecke ernste Zweifel an seiner Darstellung. Schliesslich sei festzuhalten, dass die eingereichten Arztatteste nicht geeignet sind, die geltend gemachten Folterhandlungen zu belegen. Med. pract. I._, Ärztin und Psychotherapeutin, habe beim Beschwerdeführer eine (anhaltende) posttraumatische Belastungsstörung diagnostiziert. Ihre Beurteilung, wonach die aktuelle Einschränkung des psychischen Gesundheitszustandes "ohne Zweifel im direkten Zusammenhang mit den Foltererfahrungen, die Herr A._ während seiner Inhaftierung in der Türkei in der Zeit vom 1988-1990 erlitten hat", stehe, widerspiegle dabei indessen lediglich ihre - auf einer Eigenanamnese beruhende - persönliche Meinung, welche nicht auf objektivierbaren Fakten, sondern nur auf den sich als nicht glaubhaft erweisenden Angaben des Beschwerdeführers beruhe.
4.3. Diese Ausführungen der Vorinstanz überzeugen. Eine mehrtägige Folter, die angeblich auch dann fortgesetzt wird, wenn der Betroffene die geforderte Aussage macht, erscheint nicht plausibel. Auch leuchtet nicht ein, dass der Beschwerdeführer die angeblichen Spuren nicht hat dokumentieren lassen, weder in der Türkei, wo er offenbar durch mehrere Rechtsvertreter verteidigt war, noch später während des Asylverfahrens in der Schweiz. Widersprüchlich ist auch, dass er sich in seiner Beschwerde ans Bundesgericht darauf beruft, es gebe Folterungen, die keine Spuren hinterlassen würden, nachdem er in den Asylverfahren noch vorgebracht hatte, es bestünden derartige Spuren. Zutreffend ist schliesslich der Einwand des Bundesstrafgerichts, dass das Attest der genannten Ärztin die Folter nicht beweisen kann, zumal davon auszugehen ist, dass die Ärztin bei ihrem Bericht die Darstellung des Beschwerdeführers ungeprüft als wahr unterstellt hat. Die Diagnose einer posttraumatischen Belastungsstörung bildet zudem für sich allein keinen Beweis für eine behauptete Misshandlung (BVGE D-5781/2012 vom 8. Mai 2015 E. 7 mit Hinweisen auf die medizinische Fachliteratur).
Vor diesem Hintergrund erscheint die Erstellung eines weiteren Gutachtens, wie es der Beschwerdeführer in seiner Replik beantragt, unnötig. Die Rüge der Verletzung von <ref-law> ist unbegründet.
5.
5.1. Der Beschwerdeführer macht geltend, er werde aus politischen Gründen in der Türkei zur Rechenschaft gezogen.
5.2. Gemäss Art. 3 Ziff. 1 EAUe wird die Auslieferung nicht bewilligt, wenn die strafbare Handlung, derentwegen sie beantragt wird, vom ersuchten Staat als eine politische oder als eine mit einer solchen zusammenhängende strafbare Handlung angesehen wird.
Das EAUe definiert den Begriff des politischen Delikts nicht. Art. 3 Ziff. 1 EAUe verweist in dieser Hinsicht auf die Rechtsauffassung des ersuchten Staats (<ref-ruling> E. 7b S. 409 mit Hinweis; vgl. auch <ref-ruling> E. 3 S. 299 bezüglich eines bilateralen Staatsvertrags). Dieser verfügt in dieser Frage über ein weites Ermessen (<ref-ruling> E. 3.4 S. 344; Urteil 1C_559/2011 vom 7. März 2012 E. 3.4, in: SJ 2012 I S. 401). Das Bundesgericht prüft mit freier Kognition, ob ein politisches Delikt vorliegt, das eine Auslieferung ausschliesst (<ref-ruling> E. 3.4 S. 344 mit Hinweisen).
5.3. Gemäss der bundesgerichtlichen Rechtsprechung zu Art. 3 Ziff. 1 EAUe und der entsprechenden innerstaatlichen Bestimmung von <ref-law> ist zwischen so genannt "absolut" politischen und "relativ" politischen Delikten zu unterscheiden. Absolut politische Delikte stehen in unmittelbarem Zusammenhang mit politischen Vorgängen. Darunter fallen namentlich Straftaten, welche sich ausschliesslich gegen die soziale und politische Staatsorganisation richten, wie etwa Angriffe gegen die verfassungsmässige Ordnung, Landes- oder Hochverrat. Ein relativ politisches Delikt liegt nach der Rechtsprechung vor, wenn einer gemeinrechtlichen Straftat im konkreten Fall ein vorwiegend politischer Charakter zukommt. Der vorwiegend politische Charakter ergibt sich aus der politischen Natur der Umstände, Beweggründe und Ziele, die den Täter zum Handeln bestimmt haben und die in den Augen des Rechtshilferichters vorherrschend erscheinen. Das Delikt muss stets im Rahmen eines Kampfes um die Macht im Staat begangen worden sein und in einem engen Zusammenhang mit dem Gegenstand dieses Kampfes stehen. Darüber hinaus müssen die fraglichen Rechtsgüterverletzungen in einem angemessenen Verhältnis zu den angestrebten Zielen stehen, und die auf dem Spiel stehenden politischen Interessen müssen wichtig und legitim genug sein, um die Tat zumindest einigermassen verständlich erscheinen zu lassen (Urteil 1A.181/2006 vom 23. Januar 2007 E. 3.2, nicht publ. in <ref-ruling>; <ref-ruling> E. 3.2 S. 342 f.; je mit Hinweisen).
5.4. Die dem Beschwerdeführer zur Last gelegte Tötung eines Dorfwächters kann nicht als absolut politisches Delikt betrachtet werden. Es handelt sich um eine Straftat gegen Leib und Leben, also um einen Tatbestand, der nicht unmittelbar dem Schutz der politischen und sozialen Ordnung des Staats dient (vgl. <ref-ruling> E. 6a S. 71 mit Hinweis). Das Vorbringen des Beschwerdeführers ist deshalb unter dem Titel des relativ politischen Delikts zu prüfen.
5.5. Konkret macht der Beschwerdeführer geltend, der wahre Hintergrund seiner Verurteilung in der Türkei sei der Konflikt im Dorf um die Frage der so genannten Dorfschützerthematik gewesen. Ein Teil der Bevölkerung habe eingewilligt, mit dem Staat gemeinsame Sache zu machen und bewaffnet den Schutz vor "terroristischen" Aktivitäten durchzusetzen. Ein anderer Teil der Bevölkerung, so auch er selbst, habe sich auf die Seite der aufständischen PKK bzw. des politischen Widerstandes geschlagen und habe diese tatkräftig unterstützt. Bei Auseinandersetzungen zwischen diesen lokalen Gruppen sei es zu den hier in Frage stehenden Tötungsdelikten gekommen. Es handle sich damit um politische Delikte.
5.6. Das Bundesstrafgericht bezieht sich in seinen Erwägungen im Wesentlichen auf die Entscheide der Asylbehörden, die in verschiedenen Verfahren zum Schluss gekommen sind, dass der Beschwerdeführer nach Art. 1 (F) lit. b FK vom Asyl ausgeschlossen sei. Nach dieser Bestimmung ist die Flüchtlingskonvention nicht anwendbar auf Personen, für die ernsthafte Verdachtsgründe bestehen, dass sie ein schweres Verbrechen des gemeinen Rechts ausserhalb des Gastlandes begangen haben, bevor sie dort als Flüchtling aufgenommen worden sind. Dem Beschwerdeführer hält das Bundesstrafgericht zudem vor, er argumentiere widersprüchlich, wenn er zum einen das Delikt, dessen er schuldig gesprochen worden sei, abstreite, und sich zum andern darauf berufe, es handle sich um ein politisches Delikt.
5.7. Selbst wenn eine Person die ihr vorgeworfene Tat bestreitet, steht ihr offen zu argumentieren, dass - sollte sie dennoch als Täter betrachtet werden - die Tat jedenfalls eine politische sei und der Auslieferung entgegenstehe (<ref-ruling> E. 4a S. 302 mit Hinweis). Freilich kann es in Fällen, in denen der Betroffene die Tat bestreitet, schwierig sein, deren politischen Charakter darzutun, zumal nach dem Ausgeführten dafür neben der politischen Natur der Umstände gerade auch die Beweggründe und Ziele des Täters wesentlich sind (vgl. <ref-ruling> E. 4a S. 302). Im vorliegenden Fall ist dies jedoch nicht weiter von Bedeutung. Wie aus der folgenden Erwägung hervorgeht, kann bereits anhand der äusseren Umstände, wie sie im Auslieferungsersuchen und der ihm zu Grunde liegenden Verurteilung des Beschwerdeführers zum Ausdruck kommen, ein relativ politisches Delikt ausgeschlossen werden (vgl. zur Massgeblichkeit dieser Unterlagen <ref-ruling> E. 2 S. 137 f.).
5.8. Ein Tötungsdelikt erfüllt die Voraussetzung der Verhältnismässigkeit nur ausnahmsweise, so wenn ein direkter Konnex zu einem bewaffneten Konflikt besteht oder wenn das betreffende Delikt (etwa im Fall eines "Tyrannenmords") das einzig praktikable Mittel zur Erreichung wichtiger humanitärer Ziele darstellt (<ref-ruling> E. 3.3 S. 343 mit Hinweisen). Die Tötung eines sogenannten "Dorfwächters" (vgl. dazu <ref-ruling>) ohne erkennbaren direkten Konnex zu einem bewaffneten Konflikt ist klarerweise nicht verhältnismässig in diesem Sinn. Trotz des politischen Kontextes überwiegt deshalb der gemeinrechtliche Charakter der Tat. Die vorinstanzliche Feststellung, die Tat sei nicht als relativ politisches Delikt zu qualifizieren, ist deshalb im Ergebnis nicht zu beanstanden.
6.
6.1.
6.1.1. Weiter stellt sich die Frage, ob die Voraussetzungen von Art. 3 Ziff. 2 EAUe gegeben sind. Nach dieser Vorschrift wird die Auslieferung in zwei Fällen nicht bewilligt, nämlich dann, wenn der ersuchte Staat ernstliche Gründe zur Annahme hat, dass das Auslieferungsersuchen wegen einer nach gemeinem Recht strafbaren Handlung gestellt worden ist, um eine Person aus rassischen, religiösen, nationalen oder auf politischen Anschauungen beruhenden Erwägungen zu verfolgen oder zu bestrafen, oder dass die verfolgte Person der Gefahr einer Erschwerung ihrer Lage aus einem dieser Gründe ausgesetzt wäre.
6.1.2. Die beiden Tatbestände bzw. Teilsätze der Ziff. 2 von Art. 3 EAUe erweitern den Schutzbereich von Ziff. 1. Dieser "erweiterte Schutz" ("protection élargie", vgl. Urteil 1A.268/1994 vom 26. Januar 1995 E. 6a) wird bisweilen unter dem Titel der "drohenden politischen Verfolgung" zusammengefasst oder als "Diskriminierungsklausel" bzw. "Nicht-Diskriminierungsklausel" bezeichnet ( STEFAN HEIMGARTNER, Auslieferungsrecht, 2002, S. 123; ROBERT ZIMMERMANN, La coopération judiciaire internationale en matière pénale, 4. Aufl. 2014, Rz. 629; MARTIN HEGER/KATHLEEN WOLTER, in: Rechtshilferecht in Strafsachen, 2015, 2. Hauptteil Rz. 1112).
In Bezug auf den ersten Teilsatz sind gemäss HEIMGARTNER zwei Anwendungsfälle denkbar: Entweder begehrt der ersuchende Staat die Auslieferung für ein vom Verfolgten tatsächlich begangenes gemeinrechtliches Delikt, beabsichtigt ihn aber auch wegen einer politischen Straftat zu verfolgen, oder der ersuchende Staat begehrt die Auslieferung wegen einer vom Verfolgten nicht begangenen Straftat, um ihn aus politischen Gründen zu behändigen (a.a.O., S. 123). In der Rechtsprechung wird in dieser Hinsicht von einer rein politisch motivierten bzw. fabrizierten Strafverfolgung gesprochen (<ref-ruling> E. 2c S. 378; <ref-ruling> E. 16c S. 338; Urteil 1C_559/2011 vom 7. März 2012 E. 3.5).
Der Schutzzweck des zweiten Teilsatzes erfasst die "Lage" der betroffenen Person im Allgemeinen, erstreckt sich auch auf Benachteiligungen ausserhalb des Strafverfahrens und insbesondere auf die Gefahr drohender Folter ( HEGER/WOLTER, a.a.O., 2. Hauptteil Rz. 1112). In dieser Hinsicht überschneidet sich Art. 3 Ziff. 2 zweiter Teilsatz EAUe mit einer Reihe von Garantien des Menschenrechtsschutzes (vgl. etwa bezüglich Art. 6 EMRK BGE <ref-ruling> E. 16c S. 337).
6.1.3. Die Schweiz prüft vor diesem Hintergrund die Auslieferungsvoraussetzungen des EAUe auch im Lichte ihrer völkerrechtlichen Verpflichtungen zum Schutz der Menschenrechte. Danach sind insbesondere Folter und jede andere Art grausamer, unmenschlicher oder erniedrigender Behandlung oder Bestrafung verboten (<ref-law>, Art. 3 EMRK, Art. 7 und Art. 10 Ziff. 1 UNO-Pakt II [SR 0.103.2]). Niemand darf in einen Staat ausgeliefert werden, in dem ihm Folter oder eine andere Art grausamer und unmenschlicher Behandlung oder Bestrafung droht (<ref-law>; vgl. <ref-ruling> E. 6a S. 167, 511 E. 5a S. 517; je mit Hinweisen). Auch behält sich die Schweiz die Verweigerung von Rechtshilfe vor, wenn im ersuchenden Staat die Respektierung eines Minimalstandards an Verfahrensrechten nicht gewährleistet erscheint, zumindest soweit dieser, wie das Folterverbot, zum zwingenden Völkerrecht gehört und damit sämtlichen völkervertragsrechtlichen Verpflichtungen vorgeht (vgl. Art. 53 und 64 des Wiener Übereinkommens vom 23. Mai 1969 über das Recht der Verträge [SR 0.111]; vgl. zum Ganzen: <ref-ruling> E. 4.1 S. 86 mit Hinweisen).
6.1.4. Hinweise auf eine politische Verfolgung im Sinne der beiden Tatbestände von Art. 3 Ziff. 2 EAUe können sich gemäss AHLBRECHT, BÖHM UND ROSENTHAL aus der besonderen Intensität von Verfolgungsmassnahmen, aus einem erhöhten Strafmass (sogenannter "Politzuschlag"), aus der Manipulation des Tatvorwurfs, gegebenenfalls mit der Fälschung von Beweismaterial und einer unzureichenden Sachbehandlung ergeben ( HEIKO AHLBRECHT/KLAUS-MICHAEL BÖHM/MICHAEL ROSENTHAL, in: Internationales Strafrecht in der Praxis, 2008, Rz. 692; ebenso: HEGER/WOLTER, a.a.O., 2 Hauptteil Rz. 1112).
6.1.5. Der Rechtshilferichter hat bei der Prüfung der Voraussetzungen von Art. 3 Ziff. 2 EAUe besondere Vorsicht walten zu lassen, da die Bestimmung ein Werturteil über die politischen und juristischen Verhältnisse eines Staats erfordert (<ref-ruling> E. 2a S. 376 f. mit Hinweisen). Auf der anderen Seite entbindet ihn auch etwa der Umstand, dass der ersuchende Staat Vertragspartei der EMRK ist, nicht davon, die erwähnten Garantien zu beachten und insbesondere zu überprüfen, ob die betroffene Person im Falle einer Auslieferung eine Art. 3 EMRK widersprechende Behandlung zu befürchten hätte (<ref-ruling> E. 2d S. 379).
Um den erweiterten Schutz von Art. 3 Ziff. 2 EAUe in Anspruch nehmen zu können, kann sich die auszuliefernde Person nicht darauf beschränken zu behaupten, es gehe für sie von der politisch-juristischen Situation im ersuchenden Staat eine Bedrohung aus. Es obliegt ihr vielmehr darzutun, dass ein objektives und ernsthaftes Risiko einer schweren Verletzung der Menschenrechte oder einer Diskriminierung besteht (<ref-ruling> E. 2a S. 377 mit Hinweisen).
6.2.
6.2.1. Hinsichtlich Art. 3 Ziff. 2 erster Teilsatz EAUe ist der Beschwerdeführer der Auffassung, er habe bereits in den Asylverfahren konkret aufgezeigt, dass ihm im Fall der Rückführung in die Türkei Folter drohe. Dies sei in jenen Verfahren auch anerkannt worden. Er und seine Brüder seien nach ihrer Verhaftung am 20. November 1988 mehrere Tage von der türkischen Polizei gefoltert worden. Dass Folter im Polizeigewahrsam zur damaligen Zeit ein weitverbreitetes Problem gewesen sei, räume auch die Vorinstanz ein. Der Hauptbelastungszeuge, sein Bruder H._, habe angegeben, die belastenden Aussagen gemacht zu haben, um sich von den Schlägen der Polizisten zu befreien. Die Spuren der Folter in der Türkei feststellen zu lassen, sei schwierig gewesen. Indessen gebe es mittlerweile verschiedene fachärztliche Berichte, welche eine posttraumatische Belastungsstörung diagnostizierten und diese auf die erlittene Folter zurückführten. Die erlittene Folter sei eines der Indizien für die politische Motivation der strafrechtlichen Verfolgung. Hinzu komme, dass eine lebenslängliche Strafe für eine Blutrache im osttürkischen Kontext geradezu exorbitant sei. Sein Engagement für die PKK und insbesondere der Kontakt zur obersten Führungsriege würden ebenfalls nahelegen, dass die Türkei aus politischen Gründen daran interessiert sei, seiner habhaft zu werden. Darauf weise auch der Zeitpunkt des Auslieferungsbegehrens hin. Obwohl die türkischen Behörden nachweislich schon 1992 von seinem Aufenthaltsort erfahren hätten, hätten sie erst im Jahr 2011 ein Auslieferungsgesuch gestellt. Dieses sei erfolgt, nachdem er den ranghöchsten PKK-Funktionär, der damals in Deutschland unter Hausarrest gestanden sei, besucht habe. Offenbar sei sein Auto mit Zürcher Kennzeichen dort dem türkischen Geheimdienst aufgefallen. Ein weiterer Hinweis für eine politische Verfolgung sei, dass über ihn ein politisches Datenblatt angelegt worden sei und sich dieses im Laufe des Auslieferungsverfahrens plötzlich in ein gemeinrechtliches verwandelt habe.
Der Beschwerdeführer kritisiert, das Bundesstrafgericht setze sich mit seinem Entscheid nicht nur über die genannten objektiven Anhaltspunkte für eine politische Verfolgung, sondern auch über die Entscheide der schweizerischen Asylbehörden hinweg. Diese seien jedoch auf diesem Gebiet fachkundig.
6.2.2. Das Bundesstrafgericht führt aus, die Asylbehörden seien zum Schluss gekommen, dass die Verurteilung des Beschwerdeführers rein strafrechtlichen Charakter aufweise. Sie hätten erläutert, weshalb sich aus den eingereichten Prozessakten schliessen lasse, dass der Prozess korrekt durchgeführt worden sei. Der Beschwerdeführer sei damals auch von mehreren selbst bestimmten Anwälten verteidigt und der Prozess bis zum Kassationshof weitergezogen worden. Das Gerichtsverfahren könne nicht als von vornherein unfair bezeichnet werden. Die Unschuldsbeteuerungen des Beschwerdeführers seien dagegen aufgrund verschiedener Ungereimtheiten nicht glaubhaft. Diese Einschätzung stütze sich unter anderem auf seine widersprüchlichen Aussagen zu seinem angeblichen Alibi bezüglich des Tatzeitpunktes und den konkreten Umständen, wie er vom Mord und von der gegen ihn erhobenen Anklage erfahren haben wolle. Gerade auch die vom Beschwerdeführer geltend gemachten Zweifel, die der Oberste Gerichtshof der Türkei in seinem Urteil an der Schuld des Beschwerdeführers gehegt habe, würden aufzeigen, dass entgegen der Auffassung des Beschwerdeführers sein Fall vor der Rechtsmittelinstanz unvoreingenommen geprüft und seine Verurteilung nicht leichthin erfolgt oder bereits zum Vornherein festgestanden sei.
6.2.3. Zu Recht kommt das Bundesstrafgericht gestützt auf diese Erwägungen zum Schluss, dass nicht davon auszugehen ist, das türkische Auslieferungsersuchen sei lediglich konstruiert worden, um den Beschwerdeführer wegen seiner politischen Anschauungen zu verfolgen. Was der Beschwerdeführer hiergegen vorbringt, überzeugt dagegen nicht. So erscheint eine lebenslange Freiheitsstrafe für ein Tötungsdelikt, das einer eigentlichen Exekution gleichkommt, nicht als exorbitant. Auch das politische Engagement des Beschwerdeführers, das erst spät erfolgte Auslieferungsgesuch und die Existenz eines politischen Datenblatts reichen nicht aus für die Annahme, dass die strafrechtliche Verfolgung lediglich vorgeschoben worden wäre, um eine politische Verfolgung zu kaschieren. Der angefochtene Entscheid verletzt somit Art. 3 Ziff. 2 erster Teilsatz EAUe nicht.
6.3.
6.3.1. Weiter ist zu prüfen, ob ernstlich angenommen werden muss, es bestehe die Gefahr, dass die Lage des Beschwerdeführers aus rassischen und politischen Gründen erschwert werden könnte. In dieser Hinsicht legt das Bundesstrafgericht dar, es gebe hinreichende Gründe, von der Einschätzung der Asylbehörden abzuweichen. Diese hätten verschiedene Aspekte unberücksichtigt gelassen. So bestünden Unstimmigkeiten zwischen den Aussagen des Beschwerdeführers und jenen seines Bruders C._, der ebenfalls in der Schweiz um Asyl ersucht habe. Dies gelte etwa für das PKK-Propagandamaterial, welches der Beschwerdeführer angeblich seinem Bruder übergeben habe, das von Letzterem in seinem Asylverfahren aber nicht erwähnt worden sei. Der Beschwerdeführer habe zudem im Asylverfahren vorgebracht, sein Bruder C._ werde immer wieder von der Polizei mitgenommen, geschlagen und wieder freigelassen. Nicht einsichtig sei in dieser Hinsicht, weshalb dann die Hausdurchsuchung und Festnahme von C._ erst im Herbst 1994 stattgefunden habe, also mehr als zwei Jahre nach der Einreise des Beschwerdeführers in die Schweiz. Auch habe C._ über seine eigenen politischen Aktivitäten Angaben gemacht, die mit jenen des Beschwerdeführers nicht übereinstimmten. Weiter sei unberücksichtigt geblieben, dass gemäss den Abklärungen des BFF noch im Zeitpunkt des ersten Asylentscheids vom 26. August 1994 keine politischen Datenblätter über den Beschwerdeführer, seinen Vater und seinen Bruder H._ bestanden. Aufgrund der Akten erschienen demnach die Gründe, welche zum damaligen Eintrag des Beschwerdeführers im politischen Datenblatt als "unbequeme Person" nach dessen Einreise in die Schweiz geführt hätten, insgesamt als unklar. Entsprechend lasse sich allein gestützt auf die Existenz dieses politischen Datenblatts das in der Verfügung vom 17. September 1996 angenommene Interesse der türkischen Behörden an der politischen Verfolgung des Beschwerdeführers nicht konkret nachvollziehen.
Im letzten Asylverfahren sei zudem nicht erwähnt worden, dass über den Beschwerdeführer gemäss den Abklärungen vom 23. Juli 2013 der Schweizerischen Botschaft in Ankara kein politisches Datenblatt mehr existiere, sondern nur noch ein gemeinrechtliches. Wenn das BFM zum Schluss komme, dass dem Beschwerdeführer im Fall einer Rückkehr in den Heimatstaat mit beachtlicher Wahrscheinlichkeit eine durch Art. 3 EMRK verbotene Strafe oder Behandlung drohe, so bleibe unklar, auf welche konkreten Anhaltspunkte es seine Schlussfolgerung stütze.
Gegen diese Annahme spreche zunächst, dass es sich bei der vom Beschwerdeführer geltend gemachten exilpolitischen Tätigkeit nicht um ein bedeutendes politisches Engagement handle und aktuell kein Eintrag über den Beschwerdeführer in einem politischen Datenblatt existiere. Ebenfalls stehe fest, dass seine in der Türkei lebenden Familienangehörigen und selbst seine ferienhalber mehrmals in die Türkei gereiste Ehefrau zwar über seinen Verbleib gefragt, aber darüber hinaus keinen staatlichen Repressalien ausgesetzt worden seien. Die Frage, weshalb das Auslieferungsersuchen nicht früher gestellt wurde, sei dagegen von sekundärer Bedeutung. Die auf ausdrückliche Nachfrage hin von den türkischen Behörden abgegebene Antwort erwecke keine ernsthaften Zweifel. Schliesslich habe der Beschwerdeführer nicht glaubhaft machen können, bereits vor seiner Flucht in die Schweiz vor mehr als 20 Jahren wegen seiner angeblichen Unterstützungstätigkeit für die PKK staatlichen Verfolgungsmassnahmen ausgesetzt gewesen zu sein.
Auch wenn im Falle des Beschwerdeführers eine politische Komponente durchaus bestehen möge, sei sie unter Berücksichtigung der geltend gemachten Umstände nicht dergestalt, dass eine Auslieferung a priori als ausgeschlossen erscheine. Insgesamt werde durch die von der Türkei abgegebenen Garantien der Gefahr, dass der Beschwerdeführer bei seiner Auslieferung einer Art. 3 EMRK verletzenden Behandlung und damit einer Erschwerung seiner Lage im Sinne von Art. 3 Ziff. 2 EAUe ausgesetzt sein könnte, hinreichend entgegengewirkt.
Das Bundesstrafgericht stellt schliesslich in Frage, ob sich der Beschwerdeführer überhaupt auf Art. 3 Ziff. 2 EAUe berufen könne. Er sei aufgrund des ihm angelasteten Verbrechens gemäss Art. 1 (F) lit. b FK vom Schutz der Flüchtlingskonvention ausgeschlossen. Auch wenn das EAUe einen solchen Ausschlussgrund nicht ausdrücklich vorsehe, leuchte mit Blick auf die humanitäre Zielsetzung von Art. 3 Ziff. 2 EAUe nicht ein, weshalb einer Person, welche wegen Schutzunwürdigkeit von der Flüchtlingskonvention rechtskräftig ausgeschlossen wurde, dieser Schutz auslieferungsrechtlich gewährt werden solle.
6.3.2. Nach der bundesgerichtlichen Rechtsprechung findet Art. 3 Abs. 2 EAUe auch auf Personen Anwendung, welche im Verfolgerstaat ein schweres nichtpolitisches Delikt verübt haben und deshalb nicht unter die Schutzbestimmungen der Flüchtlingskonvention fallen (Urteil 1A.127/1990 vom 18. Dezember 1990 E. 2c/aa). An dieser Rechtsprechung ist festzuhalten. Der klare Wortlaut der Bestimmung lässt in dieser Hinsicht keine Ausnahme zu. Zudem besteht nach dem Ausgeführten eine Übereinstimmung des Schutzbereichs insbesondere mit Art. 3 EMRK. Diese Norm verbietet es ebenfalls, Straftäter in einen Staat auszuliefern, in dem ihm Folter oder eine andere Art grausamer und unmenschlicher Behandlung oder Strafe drohen (<ref-ruling> E. 6.3 S. 164 mit Hinweis).
6.3.3. <ref-law> sieht vor, dass Personen, denen die Schweiz Asyl gewährt hat oder die als Flüchtlinge vorläufig aufgenommen wurden, gegenüber allen eidgenössischen und kantonalen Behörden als Flüchtlinge gelten. Diese formal-gesetzliche Bindungswirkung kommt im vorliegenden Fall nicht zur Anwendung, da der Beschwerdeführer nach Art. 1 (F) lit. b FK von der Flüchtlingseigenschaft wegen der Begehung eines schweren Verbrechens ausgeschlossen ist. Auch ausserhalb des Anwendungsbereichs von <ref-law> sind widersprüchliche Entscheide im Asyl- und im Auslieferungsverfahren indessen zu vermeiden. Der Auslieferungsrichter weicht deshalb, vorbehältlich neuer Tatsachen, im Prinzip nicht von der Sachverhaltsfeststellung der Asylbehörde ab und er weicht ohne Grund auch nicht von den Erwägungen ab, welche zur Abweisung des Asylgesuchs geführt haben (<ref-ruling> E. 2.5 S. 473 mit Hinweisen).
6.3.4. Die von der Vorinstanz dargelegten Unstimmigkeiten zwischen den Aussagen des Beschwerdeführers und denjenigen seines Bruders lassen als fraglich erscheinen, inwieweit der Beschwerdeführer bis zu seiner Verurteilung in der Türkei bereits politisch aktiv war. Dies ist jedoch nicht allein massgebend. Für die Zeit seines Aufenthalts in der Schweiz macht der Beschwerdeführer ein umfangreiches politisches Engagement geltend. Auch wenn dieses offensichtlich nicht von grosser politischer Bedeutung ist, wurde über ihn ein politisches Datenblatt mit dem Vermerk "unbequeme Person" angelegt. Aus diesem Grund und weil der Beschwerdeführer von den türkischen Behörden mit der PKK in Verbindung gebracht werde, erteilte ihm das BFF im Jahre 1996 die vorläufige Aufnahme. In seinem Entscheid vom 29. Januar 2014 hielt das BFM in dieser Hinsicht bestätigend fest, dass sich die massgebliche Sachlage nicht geändert habe.
6.3.5. Gemäss konstanter Praxis des Bundesverwaltungsgerichts ist bei Asylbewerbern aus der Türkei, für die - im Zusammenhang mit einem Strafverfahren - politische Datenblätter im so genannten Allgemeinen Informationssystem GBTS (Genel Bildi Toplama Sistemi) angelegt worden sind, in der Regel bereits aufgrund dieser Fichierung von einer begründeten Furcht vor künftiger asylrechtlich relevanter staatlicher Verfolgung auszugehen. Das GBTS sei für Polizei- und Gendarmeriestellen des ganzen türkischen Staatsgebiets, insbesondere auch für an den Landesgrenzen tätige, für Ein- und Ausreisekontrollen zuständige Einheiten zugänglich. Es sei mit Sicherheit davon auszugehen, dass das politische Datenblatt bei der mit einer Wiedereinreise verbundenen Kontrolle der betroffenen Person entdeckt werde, was bereits ein Risiko staatlicher, in ihrer Intensität asylrechtlich potenziell relevanter Verfolgungsmassnahmen darstelle. Sodann führe die Fichierung üblicherweise zu einer - möglicherweise wenig intensiven, aber zeitlich andauernden - behördlichen Überwachung. Zudem sei davon auszugehen, dass die betroffene Person bei politisch relevanten Zwischenfällen in ihrer Wohngegend häufig automatisch als potenziell tatverdächtig in Betracht gezogen und entsprechend behandelt werde (BVGE 2010/9 E. 5.3 S. 120 ff.; 2013/25 E. 5.4.3 S. 365; Urteil des BVGer D-586/2012 vom 3. März 2014 E. 4.4; vgl. auch Urteil des BVGer D-5228/2013 vom 9. Oktober 2014 E. 5.5.1). Irrelevant ist nach dieser Praxis schliesslich, ob die Strafe bereits (teilweise) verbüsst worden ist oder ob behördliche Untersuchungsmassnahmen noch hängig sind (Urteil des BVGer E-6306/2011 vom 18. Juli 2012 E. 5.2).
6.3.6. Nach dem Ausgeführten ist nur mit gutem Grund von den Sachverhaltsfeststellungen und den rechtlichen Erwägungen der Asylbehörden abzuweichen. Dies setzt, gerade auch mit Blick auf die in Frage stehenden Rechtsgüter voraus, dass durch entsprechende Abklärungen allfällige Zweifel ausgeräumt werden und feststeht, dass die Auffassung der Asylbehörden tatsächlich unzutreffend ist. Im vorliegenden Fall kann diese Voraussetzung aus folgenden Gründen zumindest im jetzigen Zeitpunkt nicht als erfüllt bezeichnet werden.
Zum einen scheint wesentlich, wann und weshalb die Fichierung des Beschwerdeführers als "unbequeme Person" erfolgt und wann und weshalb sie aufgehoben wurde. Angesichts der Bedeutung dieses Eintrags für die Feststellung einer staatlichen Verfolgung bzw. der Gefahr einer Art. 3 EMRK widersprechenden Behandlung hätte das BJ Anlass gehabt, von den türkischen Behörden eine Auskunft über die Hintergründe der Fichierung und ihrer Löschung zu verlangen. Wenn die Vorinstanz als massgeblich einzig ansieht, dass gegenwärtig kein politisches Datenblatt mehr existiert, ist ihr nicht zu folgen.
Zum andern ist nicht von der Hand zu weisen, dass der Zeitpunkt des Auslieferungsersuchens gewisse Zweifel an dessen Motivation weckt. Das BJ hat die Türkei um eine Erklärung hierzu ersucht. Die Antwort legt nahe, dass die türkische Polizei bereits im Jahr 1995 davon ausging, dass sich der Beschwerdeführer in der Schweiz befand, aber seine Adresse nicht kannte und in den folgenden Jahren auch nicht eruieren konnte. Unklar bleibt freilich, weshalb sie die Unkenntnis der genauen Adresse davon abhielt, ein Auslieferungsgesuch zu stellen.
6.3.7. Um eine gesicherte Erkenntnisgrundlage zu schaffen, die ein allfälliges Abweichen von den Entscheiden der Asylbehörden rechtfertigen könnte, hätte das Bundesamt zu den genannten Fragen weitere Abklärungen treffen müssen (vgl. Urteil 1A.129/2004 vom 8. Juli 2004 E. 3.1 mit Hinweisen). Sachdienliche Hinweise hätte wohl insbesondere auch ein Amtsbericht des SEM geben können. Die beschriebenen Unklarheiten erlauben es jedenfalls im jetzigen Zeitpunkt nicht, eine Art. 3 EMRK widersprechende Behandlung auszuschliessen. Es ist deshalb angezeigt, die Sache an das BJ zurückzuweisen.
6.3.8. Aus Gründen der Prozessökonomie ist im Folgenden auch auf die weiteren vom Beschwerdeführer erhobenen Rügen einzugehen.
7.
Der Beschwerdeführer übt unter dem Titel von Art. 3 EMRK sowie Art. 3 des Übereinkommens vom 10. Dezember 1984 gegen Folter und andere grausame, unmenschliche oder erniedrigende Behandlung oder Strafe (SR 0.105) weitere Kritik am angefochtenen Entscheid. Soweit diese nicht bereits weiter oben aufgenommen wurde, erweist sie sich jedoch nicht als stichhaltig. So ist dem Beschwerdeführer nicht zu folgen, wenn er vorbringt, Garantien durch den ersuchenden Staat seien allgemein untauglich. Es kann in dieser Hinsicht auf die publizierte Rechtsprechung verwiesen werden (betreffend die Türkei: <ref-ruling> E. 4 S. 85 ff. mit Hinweisen). Ebenfalls unbehelflich ist der Verweis des Beschwerdeführers auf seinen Gesundheitszustand. Dieser bildet grundsätzlich kein Auslieferungshindernis; zudem hat die Türkei die ausdrückliche Garantie abgegeben, während der Haft eine angemessene medizinische Betreuung zu gewährleisten (vgl. Urteil 1A.184/2002 vom 5. November 2002 E. 8, nicht publ. in <ref-ruling>). Der Gesundheitszustand des Betroffenen steht einer Auslieferung nur unter ausserordentlichen Umständen entgegen, welche hier offensichtlich nicht gegeben sind (vgl. Urteil des EGMR A.S. gegen Schweiz vom 30. Juni 2015, Beschwerde-Nr. 39350/13, §§ 31-34). Die Erstellung eines gerichtlichen Gutachtens, wie es der Beschwerdeführer in seiner Eingabe vom 15. Juni 2015 beantragt, erübrigt sich somit.
8.
8.1. In seiner Eingabe vom 15. Juni 2015 macht der Beschwerdeführer schliesslich geltend, die Vollstreckung seiner Strafe sei nach türkischem Recht verjährt, da eine entsprechende Amnestie erlassen worden sei. Die Auslieferung sei deshalb nach Art. 10 EAUe nicht möglich. Er habe in der Türkei den Rechtsweg beschritten, um die Verjährung feststellen zu lassen.
8.2. Nach Art. 10 EAUe wird die Auslieferung nicht bewilligt, wenn nach den Rechtsvorschriften des ersuchenden oder des ersuchten Staats die Strafverfolgung oder Strafvollstreckung verjährt ist. Nach der Rechtsprechung ist es grundsätzlich nicht Aufgabe der schweizerischen Behörden zu prüfen, ob die Verjährung nach dem Recht des ersuchenden Staats eingetreten ist. Ein Rechtshilfegesuch kann allenfalls abgewiesen werden, wenn die Verjährung ausser Zweifel steht (Urteil 1A.184/2005 vom 9. Dezember 2005 E. 2.11 mit Hinweisen). Dies ist hier nicht der Fall. Mit Urteil vom 22. Juni 2015 hat das 2. Schwurgericht von Gaziantep den Antrag des Beschwerdeführers abgelehnt und dargelegt, weshalb die Verjährung noch nicht eingetreten sei. Auch wenn der Beschwerdeführer diesen Entscheid als falsch bezeichnet und ein Rechtsmittel dagegen eingelegt hat, kann gestützt darauf im jetzigen Zeitpunkt nicht gesagt werden, die Verjährung sei nach türkischem Recht zweifellos eingetreten. Die Rüge der Verletzung von Art. 10 EAUe ist somit unbegründet.
9.
Zusammenfassend ergibt sich, dass die Beschwerde teilweise gutzuheissen ist. Dispositiv-Ziffer 3 des angefochtenen Entscheids ist aufzuheben und die Sache zur Neubeurteilung an das BJ zurückzuweisen. Ebenfalls aufzuheben ist Dispositiv-Ziffer 4 des angefochtenen Entscheids, wonach die Kosten des Verfahrens vor Bundesstrafgericht von Fr. 3'000.-- dem Beschwerdeführer auferlegt wurden. Die Vorinstanz wird über die Kostenliquidation in ihrem Verfahren neu zu befinden haben. Im Übrigen ist die Beschwerde abzuweisen, soweit darauf einzutreten ist.
Bei diesem Ausgang des Verfahrens obsiegt der Beschwerdeführer zum Teil. Es sind ihm reduzierte Kosten aufzuerlegen (Art. 66 Abs. 1 und 4 BGG). Der Beschwerdeführer hat zudem Anspruch auf eine reduzierte Parteientschädigung (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen. Dispositiv-Ziffer 3 und 4 des Entscheids des Bundesstrafgerichts vom 7. Mai 2015 werden aufgehoben. Die Sache wird zur neuen Beurteilung an das Bundesamt für Justiz und zur Neuverlegung der Kosten des vorinstanzlichen Verfahrens an das Bundesstrafgericht zurückgewiesen.
Im Übrigen wird die Beschwerde abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten werden im Umfang von Fr. 1'000.-- dem Beschwerdeführer auferlegt.
3.
Die Schweizerische Eidgenossenschaft hat dem Beschwerdeführer für das bundesgerichtliche Verfahren eine reduzierte Entschädigung von Fr. 3'000.-- auszurichten.
4.
Dieses Urteil wird dem Beschwerdeführer, dem Bundesamt für Justiz, Fachbereich Auslieferung, und dem Bundesstrafgericht, Beschwerdekammer, schriftlich mitgeteilt.
Lausanne, 12. August 2015
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Dold