hat sich ergeben:
A.- Der am 23. Juli 1952 geborene S._, aus dem Kosovo stammender Jugoslawe serbischer Ethnie, kam 1974 in die Schweiz. Während einiger Zeit lebte er zunächst im Kanton Luzern, später, zusammen mit seiner Frau und dem jüngsten Sohn, im Kanton Bern, wo er die Niederlassungsbewilligung erhielt, und zuletzt im Kanton Schwyz. Ein weiterer Sohn lebt ebenfalls in der Schweiz, während sich seine übrigen sieben Kinder im Ausland aufhalten.
Das Obergericht des Kantons Luzern verurteilte am 23. Dezember 1993 S._ wegen vorsätzlicher Tötung, mehrfachen vollendeten Versuchs der vorsätzlichen Tötung, alles begangen in Notwehrhilfeexzess, sowie wegen Raufhandels, mehrfacher Sachbeschädigung und mehrfachen verbotenen Waffentragens mit elf Jahren Zuchthaus und 15 Jahren Landesverweisung.
S._ erhob dagegen beim Bundesgericht je eine eidgenössische Nichtigkeitsbeschwerde und staatsrechtliche Beschwerde, welche beide erfolglos blieben (Verfahren 6P.112/1994 und 6S.503/1994).
Am 5. August 1997 entschied das Justizdepartement des Kantons Luzern, S._ bei einer Probezeit von vier Jahren bedingt aus dem Strafvollzug zu entlassen. Hingegen lehnte das Justizdepartement den probeweisen Aufschub der Landesverweisung ab. Mit Urteil vom 26. November 1997 wies das Verwaltungsgericht des Kantons Luzern eine gegen die Verweigerung des Aufschubs der Landesverweisung gerichtete Beschwerde ab. Dagegen erhob S._ Verwaltungsgerichtsbeschwerde beim Bundesgericht, welches diese am 21. Januar 1998 abwies (Verfahren 6A.109/1997).
S._ wurde am 12. Dezember 1997 bedingt aus dem Strafvollzug entlassen und der Fremdenpolizei des Kantons Luzern zur Vollstreckung der unbedingten Landesverweisung zugeführt. Gleichentags verfügte die luzernische Fremdenpolizei die Ausschaffungshaft, welche vom Einzelrichter am Verwaltungsgericht des Kantons Luzern am 16. Dezember 1997 bis zum 12. Februar 1998 genehmigt wurde. Mit Urteil vom 23. Januar 1998 hiess das Bundesgericht eine dagegen erhobene Verwaltungsgerichtsbeschwerde gut und ordnete an, S._ sei unverzüglich aus der Haft zu entlassen (Verfahren 2A.1/1998).
Mit Verfügung vom 23. Februar 1998 wies die Fremdenpolizei des Kantons Bern S._ aus der Schweiz aus.
Dieser gelangte sodann erfolglos an die Polizei- und Militärdirektion sowie an das Verwaltungsgericht des Kantons Bern. Die dagegen erhobene Verwaltungsgerichtsbeschwerde wies das Bundesgericht am 16. Februar 1999 ab (Verfahren 2A.566/1998).
Am 13. März 1999 nahm die Fremdenpolizei des Kantons Bern S._ in Ausschaffungshaft, entliess ihn aber nach der mündlichen Verhandlung beim Haftgericht III Bern-Mittelland vom 16. März 1999 auf gerichtliche Anordnung wieder.
B.- Die Fremdenpolizei des Kantons Bern ordnete am 22. November 1999 erneut die Ausschaffungshaft an. Darauf wurde S._ in Goldau/SZ am 8. April 2000 um 23:15 Uhr in Haft genommen. In der mündlichen Verhandlung vom 12. April 2000 bestätigte das Haftgericht III Bern-Mittelland diese Ausschaffungshaft. Die schriftliche Ausfertigung des Entscheids datiert vom 14. April 2000.
C.- S._ hat am 20. April 2000 (Postaufgabe
24. April 2000) Verwaltungsgerichtsbeschwerde beim Bundesgericht eingereicht mit dem Antrag, den Entscheid des Haftgerichtes III Bern-Mittelland vom 12./14. April 2000 aufzuheben und ihn unverzüglich aus der Ausschaffungshaft zu entlassen. Weiter begehrt er, die Behörden im Wege der Anordnung der aufschiebenden Wirkung "anzuweisen, von einer zwangsweisen Ausschaffung des Beschwerdeführers abzusehen, solange dieses Verfahren betreffend Ausschaffungshaft vor dem Bundesgericht hängig ist". Ausserdem ersucht er um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung.
Das Haftgericht III Bern-Mittelland (im Folgenden:
Haftrichter) und die Fremdenpolizei des Kantons Bern schliessen auf Abweisung der Beschwerde. Der Beschwerdeführer hat am 3. Mai 2000 zur Vernehmlassung der Fremdenpolizei Stellung genommen und an seinen Anträgen festgehalten.
Des Eidgenössische Justiz- und Polizeidepartement hat sich nicht vernehmen lassen.

Das Bundesgericht zieht in Erwägung:
1.- Gegenstand des Verfahrens bildet ausschliesslich die Rechtmässigkeit und Angemessenheit der Haft als solcher, nicht auch die Ausweisung und die Ausschaffung (vgl. <ref-ruling> E. 2 S. 220). Daher ist auf das Begehren des Beschwerdeführers, von einer zwangsweisen Ausschaffung einstweilen abzusehen, nicht einzutreten.
2.- Die zuständige Behörde kann einen Ausländer in Ausschaffungshaft nehmen bzw. in dieser belassen, soweit die Voraussetzungen von Art. 13b des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142. 20) erfüllt sind. Demnach ist erforderlich, dass ein erstinstanzlicher, nicht notwendigerweise auch rechtskräftiger Weg- oder Ausweisungsentscheid vorliegt (vgl. <ref-ruling> E. 2a S. 61; <ref-ruling> E. 1 S. 150), dessen Vollzug (z.B. wegen fehlender Reisepapiere) noch nicht möglich, jedoch absehbar ist (<ref-ruling> E. 2b S. 379, mit Hinweis).
Zudem muss einer der in Art. 13b Abs. 1 ANAG genannten Haftgründe bestehen (<ref-ruling> E. 3a S. 381 mit Hinweis), die Ausschaffung rechtlich und tatsächlich möglich sein (Art. 13c Abs. 5 lit. a ANAG; vgl. dazu BGE <ref-ruling> E. 3 S. 152 ff.) und die Papierbeschaffung mit dem nötigen Nachdruck verfolgt werden (Art. 13b Abs. 3 ANAG; Beschleunigungsgebot; <ref-ruling> E. 3 S. 50 ff.).
3.- Sowohl der Haftrichter als auch die Fremdenpolizei des Kantons Bern berufen sich für die Ausschaffungshaft zunächst auf Art. 13b Abs. 1 lit. b in Verbindung mit Art. 13a Abs. 1 lit. e ANAG und die strafrechtliche Verurteilung des Beschwerdeführers vom 23. Dezember 1993.
Wie das Bundesgericht bereits anlässlich der von der Fremdenpolizei des Kantons Luzern gegen den Beschwerdeführer verfügten Ausschaffungshaft ausgeführt hatte, scheidet dieser Haftgrund aus, sofern der Beschwerdeführer seit dem 1. Februar 1995 kein gefährliches Verhalten mehr gezeigt hat, das Anlass zu einer Strafverfolgung gegeben hat (E. 3 des Urteils des Bundesgerichts vom 23. Januar 1998 im Verfahren 2A.1/1998, vgl. Art. 2 der Schlussbestimmungen zum Bundesgesetz vom 18. März 1994 über Zwangsmassnahmen im Ausländerrecht [AS 1995 146]). Da die strafrechtliche Verurteilung eine am 15. August 1990 begangene Tat betrifft und der Beschwerdeführer nach Aktenlage seit dem 1. Februar 1995 kein gefährliches Verhalten mehr gezeigt hat, scheidet ein Haftgrund nach Art. 13b Abs. 1 lit. b in Verbindung mit Art. 13a lit. e ANAG aus.
4.- a) Der Haftrichter stützt seinen Entscheid des Weiteren auf Art. 13b Abs. 1 lit. c ANAG. Demnach kann Ausschaffungshaft verfügt werden, wenn konkrete Anzeichen befürchten lassen, dass sich der Ausländer der Ausschaffung entziehen will (Gefahr des Untertauchens). Der Vollzug der Wegweisung muss erheblich gefährdet erscheinen. Dass der Betroffene einer Ausreiseanordnung nicht Folge geleistet hat und sich illegal in der Schweiz aufhält, genügt hierfür allein ebensowenig wie die Tatsache, dass er keine Papiere besitzt und nur mangelhaft an deren Beschaffung mitwirkt.
Dagegen ist Untertauchensgefahr anzunehmen, wenn der Ausländer bereits einmal untergetaucht ist, behördlichen Anordnungen keine Folge leistet oder durch erkennbar unglaubwürdige und widersprüchliche Angaben die Vollzugsbemühungen der Behörden erschwert. Bei einem straffälligen Ausländer ist eher als bei einem unbescholtenen davon auszugehen, er werde in Zukunft behördliche Anordnungen missachten. Das Fehlen eines festen Aufenthaltsorts oder Mittellosigkeit genügen für sich allein nicht für die Annahme von Untertauchensgefahr, können diese jedoch gegebenenfalls zusammen mit anderen Hinweisen indizieren. Für die Gefahr des Untertauchens spricht, wenn der Ausländer klar zu erkennen gibt, dass er keinesfalls in sein Herkunftsland zurückkehren will. In diesem Fall bietet er keine Gewähr dafür, dass er sich zu gegebener Zeit, wenn die Reisepapiere vorliegen, für den Vollzug der Ausschaffung zur Verfügung halten wird (<ref-ruling> E. 2a S. 50 f., mit Hinweisen).
b) Die Vorinstanz leitet die Untertauchensgefahr zunächst erneut aus den strafrechtlich relevanten Handlungen des Beschwerdeführers ab, für die er vor dem 1. Februar 1995 verurteilt wurde. Auch insoweit besteht aber derselbe Einwand wie für den Haftgrund nach Art. 13a lit. e ANAG: Das Verhalten des Beschwerdeführers im Zusammenhang mit der Tatbegehung darf nur berücksichtigt werden, wenn es auch haftbegründende Vorkommnisse gibt, die nach Inkrafttreten des Zwangsmassnahmengesetzes eingetreten sind (E. 4b des erwähnten Urteils vom 23. Januar 1998, vgl. auch BGE <ref-ruling> E. 2a S. 151, mit Hinweisen).
Der Haftrichter beruft sich zudem darauf, der Beschwerdeführer habe anlässlich der Haftprüfung vom 16. März 1999 versichert, bereit zu sein, freiwillig die vorgesehene Ausreise - gebuchter Flug vom 29. März 1999 in den Kosovo - anzutreten, er dies dann jedoch nicht getan habe. Der Krieg im Kosovo sei inzwischen beendet, er könne sich als Serbe auch in einem andern Teil Jugoslawiens niederlassen, ihm sei eine Ausreise seit einiger Zeit möglich und ihm müsse klar sein, dass er die Schweiz zu verlassen habe. Anlässlich der mündlichen Verhandlung vom 12. April 2000 habe er zu erkennen gegeben, "er bedürfe einer Sonderregelung, hier zu bleiben und wolle nicht zurück in sein Heimatland".
c) Es ist gerichtsbekannt, dass im Jahre 1999 Krieg im Kosovo herrschte und das Nato-Bündnis seit Ende März 1999 Luftangriffe auf Jugoslawien unternahm. Während der mehrwöchigen Kämpfe waren Flüge von der Schweiz nach Jugoslawien nicht möglich. Zudem ergibt sich aus den Akten, dass die Fremdenpolizei des Kantons Luzern den für den 29. März 1999 angesetzten Flug des Beschwerdeführers annullierte. Sodann verfügte der Beschwerdeführer schon im Zeitpunkt der mündlichen Verhandlung vom 16. März 1999 über keinen gültigen Ausweis mehr. Die Gültigkeit des von den Fremdenpolizeibehörden besorgten Passierscheines ist am 16. September 1999 ausgelaufen. In einem Schreiben der Rechtsvertreterin des Beschwerdeführers, welches der Fremdenpolizei des Kantons Bern am 30. März 1999 zuging, wurden die Behörden darauf hingewiesen, dass der Beschwerdeführer unter anderem beim jugoslawischen Konsulat vorgesprochen habe, welches von ihm für die Ausstellung eines Reisedokumentes die Vorlage eines Heimatscheines gefordert hätte; der im Kosovo liegende Heimatort habe ihm einen solchen Schein jedoch nicht ausgestellt, weil er in keinem Register zu finden sei; weitere Bemühungen um den Erhalt eines solchen Scheines seien ebenfalls ergebnislos verlaufen; abschliessend wurden die Behörden um Verlängerung der Ausreisefrist gebeten. Auf dieses Schreiben antwortete die Fremdenpolizei des Kantons Bern offenbar nicht. Zu einem sich aus den Akten nicht ergebenden Zeitpunkt ersuchte sie die Behörden des Kantons Schwyz, den Beschwerdeführer zwecks Ausschaffungshaft festzunehmen. In ihrer Haftanordnung vom 22. November 1999 bezeichnete sie als Ausreisefrist den 3. Januar 2000. Aus den Akten ergibt sich indes nicht, dass sie diesen Termin dem Beschwerdeführer bekannt gegeben hätte. Warum der Beschwerdeführer, dessen Festnahme ursprünglich zu diesem Datum erfolgen sollte, letztlich erst am 8. April 2000 verhaftet wurde, erschliesst sich ebenso wenig aus den Akten. Die Behörden gehen selber davon aus, dass sich der Beschwerdeführer immer an der Adresse aufgehalten hat, wo er festgenommen wurde. Den Akten ist nicht zu entnehmen, dass der Beschwerdeführer zu irgendeinem Zeitpunkt versucht hätte, unterzutauchen oder sonst wie die Vollzugsbemühungen der Behörden zu erschweren.
Im Haftprüfungstermin vom 12. April 2000 erklärte der Beschwerdeführer:
"Falls ich ausgeschafft werden soll, dann bleibt mir wohl nichts Anderes übrig, aber ich möchte hier bleiben". Die sodann nicht protokollierte Aussage, dass er einer "Sonderregelung bedürfe", erläutert der Beschwerdeführer mit seinem Wunsch nach einer Revision oder Begnadigung angesichts der besonderen Umstände in seiner Heimat.
Damit ist im jetzigen Zeitpunkt, in dem noch nicht einmal die benötigten Ausreisedokumente vorliegen, der Haftgrund der Untertauchensgefahr nicht erfüllt. Zwar mag sich der Beschwerdeführer kaum aktiv um seine Ausreise bemüht haben. Sein Gesamtverhalten deutet eher darauf hin, dass er abwartet, bis er ausgeschafft werde, als dass er das Land auf eigenes Betreiben verlässt. Nach ständiger Rechtsprechung des Bundesgerichts genügt bloss passives Verhalten indes nicht bereits, um den Haftgrund der Untertauchensgefahr anzunehmen (<ref-ruling> E. 2a S. 50 f.). Das Gesetz will nicht präventiv die kontrollierte Ausreise jedes Ausländers sicherstellen (Alain Wurzburger, La jurisprudence récente du Tribunal fédéral en matière de police des étrangers, in RDAF 1997 1 S. 267 ff., insbes. S. 332; AndreasZünd, Die Rechtsprechung des Bundesgerichts zu den Zwangsmassnahmen im Ausländerrecht, in ZBJV 132/1996 S. 72 ff., insbes. S. 87). Vielmehr müssen für die Ausschaffungshaft konkrete Anzeichen befürchten lassen, dass sich der Betroffene der Ausschaffung entziehen will. Die von den Behörden präsentierten Akten enthalten keine derartigen hinreichenden Hinweise, zumal der Beschwerdeführer bis zu seiner Verhaftung im April 2000 offenbar keine Anstalten getroffen hatte, um unterzutauchen.
5.- a) Da nach dem Dargelegten die geltend gemachten Haftgründe nicht erfüllt sind, erweist sich die Verwaltungsgerichtsbeschwerde als begründet, soweit darauf einzutreten ist. Dementsprechend ist der Beschwerdeführer unverzüglich aus der Haft zu entlassen.
b) Den kantonalen Behörden ist es selbstverständlich nicht verwehrt, die nötigen Vorkehren für die Ausschaffung des Beschwerdeführers zu treffen. Sie können ihn verpflichten, sich für weitere Abklärungen bzw. für die Durchführung der Ausschaffung zur Verfügung zu halten. Sollten Haftgründe eintreten, namentlich sich für ein künftiges Untertauchen sprechende Anhaltspunkte ergeben, läge ein neuer Sachverhalt vor, der Grundlage für die Anordnung der Ausschaffungshaft bilden könnte.
6.- Da der Beschwerdeführer obsiegt, ist keine Gerichtsgebühr zu erheben (Art. 156 Abs. 2 OG). Der Kanton Luzern hat den anwaltlich vertretenen Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 159 Abs. 1 und 2 OG). Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird damit gegenstandslos.

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird, soweit darauf einzutreten ist, gutgeheissen, und der Entscheid des Haftgerichts III Bern-Mittelland, Haftrichter 3, vom 14. April 2000 wird aufgehoben.
2.- Der Beschwerdeführer ist unverzüglich aus der Haft zu entlassen.
3.- Es werden keine Kosten erhoben.
4.- Der Kanton Bern hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 1'500.-- zu entschädigen.
5.- Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird als gegenstandslos abgeschrieben.
6.- Dieses Urteil wird dem Beschwerdeführer, der Fremdenpolizei des Kantons Bern und dem Haftgericht III Bern-Mittelland, Haftrichter 3, sowie dem Eidgenössischen Justiz- und Polizeidepartement schriftlich (dem Beschwerdeführer und der Fremdenpolizei auch per Fax) mitgeteilt.
_
Lausanne, 8. Mai 2000
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: