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.