Auslieferung an Deutschland - B 119746, hat sich ergeben:
A.-Gestützt auf einen Haftbefehl des Amtsgerichtes Oberhausen vom 2. März 2000 ersuchte das Justizministerium des Landes Nordrhein-Westfalen das Bundesamt für Polizei (BAP) am 17. März 2000 um Auslieferung des bosnischen Staatsangehörigen X._. Diesem wird vorgeworfen, er habe am 25. Januar 2000 in Oberhausen/D A._ mit mehreren Schüssen aus einer Handfeuerwaffe getötet und B._ schwer verletzt.
B.- Am 8. März 2000 erliess das BAP gegen X._ einen Auslieferungshaftbefehl. Anlässlich seiner Befragung vom 6. April 2000 widersetzte sich der Verfolgte einer vereinfachten Auslieferung nach Deutschland. Mit Entscheid vom 2. Mai 2000 bewilligte das BAP die Auslieferung.
C.-Dagegen gelangte X._ mit Verwaltungsgerichtsbeschwerde vom 29. Mai 2000 an das Bundesgericht.
Er stellt folgendes Rechtsbegehren:
"1. Es sei der Entscheid des Eidgenössischen Justiz- und Polizeidepartementes, Bundesamt für Polizei,
vom 2. Mai 2000 (...) aufzuheben und die Auslieferung
des Verfolgten und Beschwerdeführers an
Deutschland zu verweigern.
2. Es sei der Verfolgte und Beschwerdeführer unverzüglich
aus seiner Auslieferungshaft zu entlassen.. "
D.-Das Bundesamt für Polizei beantragt mit Stellungnahme vom 14. Juni 2000 die Abweisung der Beschwerde. Der Beschwerdeführer erhielt Gelegenheit zur Replik.

Das Bundesgericht zieht in Erwägung:
1.-a) Die Beurteilung von Auslieferungsersuchen der Bundesrepublik Deutschland richtet sich nach dem Europäischen Auslieferungsübereinkommen vom 13. Dezember 1957 (EAUe, SR 0.353. 1) sowie dem Zweiten Zusatzprotokoll zum EAUe vom 17. März 1978, dem beide Staaten beigetreten sind (SR 0.353. 12). Soweit das EAUe gewisse Fragen nicht abschliessend regelt (vgl. <ref-ruling> E. 2d S. 283), ist das schweizerische Landesrecht anwendbar, namentlich das Bundesgesetz über internationale Rechtshilfe in Strafsachen vom 20. März 1981 (IRSG, SR 351. 1) und die dazugehörende Verordnung vom 24. Februar 1982 (IRSV, SR 351. 11; vgl. <ref-law>).
b) Der Auslieferungsentscheid des BAP vom 2. Mai 2000 kann mit Verwaltungsgerichtsbeschwerde beim Bundesgericht angefochten werden (Art. 55 Abs. 3 i.V.m. <ref-law>). Die Sachurteilsvoraussetzungen von Art. 97 - 114 OG sind erfüllt.
c) Zulässige Beschwerdegründe sind sowohl die Verletzung von Bundesrecht und internationalem Staatsvertragsrecht, einschliesslich Überschreitung oder Missbrauch des Ermessens, als auch die Rüge der unrichtigen oder unvollständigen Feststellung des rechtserheblichen Sachverhalts.
Der Vorbehalt von Art. 105 Abs. 2 OG trifft hier nicht zu (Art. 104 lit. a - b OG; <ref-ruling> E. 2b/bb S. 72).
Soweit die Verwaltungsgerichtsbeschwerde gegeben (und die staatsrechtliche Beschwerde daher ausgeschlossen) ist, kann auch die Verletzung verfassungsmässiger Individualrechte bzw. der EMRK mitgerügt werden (<ref-ruling> E. 1b S. 375).
d) Das Bundesgericht ist an die Begehren der Parteien nicht gebunden (<ref-law>). Es prüft die Auslieferungsvoraussetzungen grundsätzlich mit freier Kognition.
Da es aber in Rechtshilfesachen nicht Aufsichtsbehörde ist, darf die Prüfung des angefochtenen Entscheides den Rahmen des Streitgegenstandes nicht sprengen (<ref-ruling> E. 2c S. 73; <ref-ruling> E. 3 S. 586, je mit Hinweisen).
2.- Der Beschwerdeführer bringt vor, er könne "für die Tatzeit ein Alibi" nachweisen, und "gemäss <ref-law>" wäre "das BAP verpflichtet" gewesen, diesbezüglich "selber Abklärungen vorzunehmen".
a) Das IRSG regelt die Auslieferung strafrechtlich verfolgter Personen nur soweit, als internationale Vereinbarungen nichts anderes bestimmen (<ref-law>). Die materiellen und formellen Voraussetzungen für eine Auslieferung an Deutschland sind im EAUe geregelt.
Soweit das IRSG eine Auslieferung an einschränkendere Voraussetzungen knüpft, ist somit das EAUe massgeblich.
b) Im Gegensatz zu <ref-law> sieht das EAUe den Alibibeweis des Verfolgten als Auslieferungshindernis nicht ausdrücklich vor. Trotz der in Art. 1 EAUe verankerten grundsätzlichen Auslieferungspflicht ist der Möglichkeit eines Alibibeweises jedoch nach der Praxis des Bundesgerichtes auch im Rahmen eines gemäss EAUe durchgeführten Auslieferungsverfahrens angemessen Rechnung zu tragen. Es würde den allgemeinen Prinzipien des Auslieferungsrechtes und auch dem Verhältnismässigkeitsgebot widersprechen, einen offensichtlich Unschuldigen auszuliefern. Den Alibibeweis kann der Verfolgte allerdings nur mit dem Nachweis führen, dass er zur fraglichen Zeit überhaupt nicht am Tatort war.
Dieser Nachweis ist unverzüglich und ohne Weiterungen zu erbringen (<ref-ruling> E. 2b S. 281 f.; <ref-ruling> E. 3b - c S. 281 - 283, je mit Hinweisen.).
3.-Der Beschwerdeführer macht geltend, im Auslieferungsersuchen werde "lediglich das Datum" der untersuchten Straftaten erwähnt. Es enthalte jedoch "keine Hinweise, um welche Uhrzeit" diese erfolgten. "Aus den weiteren Akten" gehe allerdings hervor, dass die Tötungsdelikte "zur frühen Abendzeit des 25. Januar 2000 begangen worden" seien.
Der Beschwerdeführer legt nicht dar, aus welchen "weiteren Akten" sich die "frühe Abendzeit" als Tatzeitpunkt ergebe. Er verweist in diesem Zusammenhang lediglich auf seine eigenen Aussagen anlässlich polizeilicher Einvernahmen (vgl. Beschwerdeschrift, S. 3 Ziff. 3). Weder im Auslieferungsersuchen vom 17. März 2000 noch im Haftbefehl des Amtsgerichtes Oberhausen vom 2. März 2000 wird der genaue Zeitpunkt der untersuchten Delikte näher konkretisiert.
Im Haftbefehl wird der "25. 01.2000" als Datum der Tötungsdelikte genannt, als Tatort die "C._ Strasse 14" in Oberhausen/D. Anlässlich der Einvernahme durch die Kantonspolizei Zürich vom 6. April 2000 wurde der Beschwerdeführer gefragt: "wieso haben Sie Einwände gegen den Auslieferungshaftbefehl bzw. gegen die Auslieferung?".
Darauf gab er zu Protokoll, "zum Zeitpunkt der Tat" sei er "nicht in Oberhausen" gewesen. Er habe sich "am 25.01.2000 mit einem Albaner in Frankfurt getroffen, zwischen 19.00 Uhr und 19.30 Uhr". Anschliessend habe er mit dieser Person, deren Namen er nicht kenne, "ein Nachtessen eingenommen".
Zum Zwecke des Alibinachweises bringt der Beschwerdeführer weiter vor, er habe Oberhausen am 25. Januar 2000 "zwischen 15.30 und 15.45 Uhr (...) in Richtung Frankfurt" verlassen. Nach dem Abendessen mit dem erwähnten Albaner habe er in Neu-Isenburg ein jugoslawisches Café aufgesucht.
Anschliessend habe er "eine Kollegin" der "dort arbeitenden Serviertochter" mit dem Auto nach Hause gebracht und sein Fahrzeug betankt. Es seien ihm unterdessen Beweismittel zugegangen, welches diese Sachdarstellung beweisen würden. Er habe herausgefunden, dass es sich beim fraglichen Albaner um einen "Y._" handle. Dieser habe "am 15. Mai 2000 vor dem Gemeindegericht in Godine" (recte: Pirot) "eine Erklärung zu Protokoll gegeben". Darin bestätige Y._ "ausdrücklich, mit dem Beschwerdeführer am 25. Januar 2000 um 19.15 Uhr im Restaurant 'D._' in Frankfurt zusammen getroffen" und "mit ihm bis 22.00 Uhr zusammen gewesen" zu sein. Weil sich die Gewährsperson "zu jener Zeit illegal in der Bundesrepublik Deutschland aufgehalten" habe, habe sie "weder dort noch in der Schweiz vor den Untersuchungsbeamten aussagen" wollen. "Auch für die Aussage des Beschwerdeführers, er habe in Frankfurt den von ihm gesteuerten Personenwagen betankt", seien "am 26. Mai 2000 Beweismittel eingegangen".
4.-Es erscheint zum Vornherein fraglich, ob die Ausführungen des Beschwerdeführers zu seinem angeblichen Aufenthaltsort am 25. Januar 2000 ab 15.30 Uhr für einen Alibibeweis überhaupt tauglich wären, zumal weder das Auslieferungsersuchen noch dessen Beilagen einen Tatzeitpunkt vor 15.30 Uhr ausschliessen. Aber selbst wenn von einem Tatzeitpunkt "zur frühen Abendzeit" auszugehen wäre, wie es der Beschwerdeführer behauptet, könnte gestützt auf die von ihm eingereichten Unterlagen nicht ohne Weiterungen ein liquider Alibibeweis erbracht werden.
a) Diesbezüglich drängt sich namentlich die Frage auf, inwiefern die vom Beschwerdeführer vorgelegten Dokumente authentisch sind, um wen es sich bei der mit "Y._" bezeichneten Person handelt und inwiefern dessen angebliche Aussagen glaubwürdig erscheinen bzw.
korrekt protokolliert und übersetzt wurden. Aus den eingereichten Nachforschungsunterlagen der Post ginge lediglich hervor, dass der Beschwerdeführer am 2. März 2000 einen Betrag von DEM 40.05 zugunsten einer Tankstelle in Neu-Isenburg/D überweisen liess. Den Unterlagen kann hingegen weder die Uhrzeit noch das Datum des Benzinbezuges entnommen werden.
b) Auch bei Auslieferungsbegehren gestützt auf das EAUe ist der Rechtshilferichter grundsätzlich an die Sachverhaltsdarstellung der ersuchenden Behörde gebunden (<ref-ruling> E. 2b S. 281; vgl. auch <ref-ruling> E. 5b S. 257; <ref-ruling> E. 7b S. 137, 367 E. 2c S. 371; <ref-ruling> E. 5c S. 255; <ref-ruling> E. 5b S. 121 f.; <ref-ruling> E. 5c S. 88, je mit Hinweisen). Über die formellen und materiellen Auslieferungsvoraussetzungen des hier massgeblichen EAUe hinaus hat der Rechtshilferichter weder ein Beweisverfahren durchzuführen, noch - dem Sachrichter vorgreifend - bereits eine strafrechtliche Beweiswürdigung vorzunehmen. Im Falle einer Anklageerhebung wird es vielmehr Aufgabe des erkennenden Strafrichters sein zu beurteilen, ob sich angesichts der eingereichten Dokumente Zweifel am belastenden Beweismaterial bzw. an der Täterschaft des Angeklagten aufdrängen. Nach der Praxis des Bundesgerichtes ist es auch nicht Aufgabe des Rechtshilferichters, die Glaubwürdigkeit und Authentizität von privat erhobenen Aussagen zu prüfen, die Drittpersonen nach Darlegung des Verfolgten im Ausland gemacht hätten.
c) Gestützt auf die vorliegenden Akten erscheint der Beschwerdeführer nicht als offensichtlich unschuldige Person im Sinne der dargelegten Rechtsprechung. Ebenso wenig liegt hier ein klarer, liquider Fall eines Alibibeweises im Sinne von <ref-law> vor.
5.-Auch die Rüge, das Auslieferungsbegehren sei in formeller Hinsicht ungenügend, erweist sich als unbegründet.
a) Der Beschwerdeführer macht geltend, gemäss <ref-law> und <ref-law> sei der wesentliche Sachverhalt "im Ersuchen selbst" anzuführen. Dazu gehöre "neben den Angaben des Begehungsortes und der Art der Tatbegehung auch die genaue Tatzeit". Das Ersuchen erwähne "lediglich das Datum der Tat", es enthalte indessen keine Hinweise, um welche Uhrzeit diese Tat ausgeführt wurde".
b) Für das vorliegende Auslieferungsverfahren sind (wie bereits erwähnt) die materiellen und formellen Bestimmungen des EAUe massgeblich. Das Landesrecht ist allenfalls subsidiär anwendbar, wenn eine staatsvertragliche Regelung fehlt oder lückenhaft ist oder wenn das nationale Recht geringere Anforderungen an die Rechtshilfe stellt und deshalb nach dem Günstigkeitsprinzip zur Anwendung gelangt (<ref-law>; vgl. <ref-ruling> E. 2 S. 141 f., 485 E. 1 und 3a - b S. 486 f., je mit Hinweisen). Art. 12 Ziff. 2 lit. b EAUe verlangt in formeller Hinsicht eine Darstellung der Handlungen, derentwegen um Auslieferung ersucht wird.
Zeit und Ort ihrer Begehung sind "so genau wie möglich" anzugeben.
Die notwendigen Sachverhaltsangaben können sich sowohl aus dem Ersuchen als auch aus dessen Beilagen und allfälligen Ergänzungen ergeben (vgl. Art. 13 EAUe, <ref-law>).
c) Im Haftbefehl des Amtsgerichtes Oberhausen wird (knapp aber ausreichend) dargelegt, dass der Beschwerdeführer verdächtigt werde, A._ am 25. Januar 2000 an der C._ Strasse 14 in Oberhausen (im Rahmen einer "Abrechnung" im Zuhältermilieu) mit mehreren Schüssen aus einer Handfeuerwaffe getötet und B._ (ebenfalls mit mehreren Schüssen) schwer verletzt zu haben. Letzterer habe nur dank sofortiger intensivmedizinischer Hilfe überlebt.
Entgegen der Auffassung des Beschwerdeführers erfüllt diese Sachverhaltsdarstellung sowohl die formellen Voraussetzungen des EAUe als auch diejenigen von <ref-law>, der "eine kurze Darstellung des wesentlichen Sachverhalts" verlangt. Zwar wäre es durchaus hilfreich gewesen - namentlich im Zusammenhang mit der Überprüfung von Alibiangaben -, wenn dem Ersuchen und dessen Beilagen noch präzisere Angaben zur mutmasslichen Tatzeit hätten entnommen werden können.
Daraus ergibt sich jedoch im vorliegenden Fall kein Rechtshilfehindernis.
Die Sachverhaltsangaben sollen es dem Rechtshilferichter ermöglichen, die rechtlichen Voraussetzungen der ersuchten Auslieferung zu prüfen. Wie sich aus den Erwägungen 2 - 4 ergibt, läge selbst dann kein liquider Alibibeweis vor, wenn die ersuchende Behörde die Tatzeit näher (nämlich, wie der Beschwerdeführer geltend macht, auf den Zeitpunkt des frühen Abends) konkretisiert hätte.
6.-Aus dem Gesagten folgt, dass die Beschwerde als unbegründet abzuweisen ist.
Da kein Auslieferungshindernis besteht, kann in diesem Zusammenhang auch dem Rechtsbegehren nach Entlassung aus der Auslieferungshaft nicht stattgegeben werden.
Dem Ausgang des Verfahrens entsprechend, sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (Art. 156 Abs. 1 OG).

Demnach erkennt das Bundesgericht:
1.-Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2.-Die Gerichtsgebühr von Fr. 3'000.-- wird dem Beschwerdeführer auferlegt.
3.-Dieses Urteil wird dem Beschwerdeführer sowie dem Bundesamt für Polizei, Abteilung Internationales, Sektion Auslieferung, schriftlich mitgeteilt.
_
Lausanne, 26. Juni 2000
Im Namen der I. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: