wird festgestellt und in Erwägung gezogen:
1.- a) Der albanische Staatsangehörige M._, geb. 1983, befindet sich seit dem 5. Oktober 1999 in Ausschaffungshaft.
Am 7. Oktober 1999 genehmigte das Haftgericht III Bern-Mittelland die erstmalige Haftanordnung, und am 3. Januar 2000 bewilligte dasselbe Gericht die Haftverlängerung bis zum 4. April 2000. Am 30. März 2000 verlängerte die Haftrichterin 6 am Haftgericht III Bern-Mittelland die Haft um erneut drei Monate bis zum 4. Juli 2000.
b) Mit handschriftlicher Eingabe in französischer Sprache vom 8. April 2000 (Postaufgabe: 10. April 2000) an das Bundesgericht wendet sich M._ gegen das haftrichterliche Urteil vom 30. März 2000. Er verlangt die Überprüfung des Entscheids und ersucht sinngemäss um Haftentlassung.
Das Haftgericht III Bern-Mittelland sowie die Fremdenpolizei der Stadt Bern schliessen auf Abweisung der Beschwerde.
Das Eidgenössische Justiz- und Polizeidepartement hat sich innert Frist nicht vernehmen lassen. Der Beschwerdeführer nahm die Gelegenheit nicht wahr, sich nochmals zur Sache zu äussern.
2.- a) Die Verwaltungsgerichtsbeschwerde ist offensichtlich unbegründet und im vereinfachten Verfahren nach Art. 36a OG mit summarischer Begründung abzuweisen.
b) Nachdem der Beschwerdeführer bereits am 5. August 1999 durch die Behörden des Kantons Zürich ausgeschafft worden ist, erweist sich die mit dem Asylentscheid vom 3. Mai 1999 verfügte Wegweisung als vollzogen. Nach seiner erneuten Einreise konnte der Beschwerdeführer indes in Anwendung von Art. 12 Abs. 1 ANAG formlos weggewiesen werden.
Sein renitentes Verhalten wie auch der Umstand, dass er bereits früher einmal untergetaucht war, lassen erkennen, dass er sich bei einer allfälligen Haftentlassung den Behörden nicht für die Ausschaffung zur Verfügung halten würde. Damit sind die Voraussetzungen des Haftgrundes der Untertauchensgefahr gemäss Art. 13b Abs. 1 lit. c ANAG erfüllt (vgl.
BGE 125 II 369 E. 3b/aa S. 375; <ref-ruling> E. 2a; <ref-ruling> E. 2b S. 198). An sich gälte dies wohl auch für den Haftgrund der Einreise trotz Bestehens einer Einreisesperre gemäss Art. 13b Abs. 1 lit. b in Verbindung mit Art. 13a lit. c ANAG; nachdem das Haftgericht diesen Haftgrund aber nie geprüft hat und ohnehin ein anderer Haftgrund gegeben ist, kann offen bleiben, ob auch dieser zweite Haftgrund besteht.
c) Bis heute hat sich der Beschwerdeführer äusserst renitent verhalten und die nötige Mitwirkung bei der Identitätsabklärung und der Beschaffung von Reisepapieren verweigert.
Damit stehen dem Vollzug der Wegweisung besondere Hindernisse entgegen, weshalb die Haft in Anwendung von Art. 13b Abs. 2 ANAG verlängert werden darf. Angesichts des Verhaltens des Beschwerdeführers erweist sie sich auch im Hinblick auf die Dauer als verhältnismässig.
d) In den Monaten Oktober bis Dezember 1999 gelangten die bernischen Behörden mehrfach an die albanische Botschaft, um für den Beschwerdeführer Reisepapiere zu beschaffen.
Dieser hat nie bestritten, albanischer Staatsangehöriger zu sein, weigerte sich aber entgegen der ihm obliegenden Mitwirkungspflicht konstant, die von der Botschaft als mangelhaft erkannten Angaben zu seiner Person zu vervollständigen.
Im Januar und Februar 2000 versuchten die kantonalen Behörden wiederholt, die persönlichen Daten durch Befragung des Beschwerdeführers zu ergänzen. Am 6. März 2000 ersuchten sie das Bundesamt für Flüchtlinge um Hilfe beim Vollzug der Wegweisung. Am 14. März 2000 gelangte auch dieses an die albanische Botschaft, und am 28. März 2000 fragte es die schweizerische Botschaft in Albanien an, vor Ort ergänzende Abklärungen zur Person des Beschwerdeführers vorzunehmen.
Damit sind die Behörden bisher ihrer Pflicht nach Art. 13b Abs. 3 ANAG, die für die Wegweisung notwendigen Vorkehren umgehend zu treffen (sog. Beschleunigungsgebot), klarerweise nachgekommen.
e) Das Vorgehen der bernischen Behörden ist auch nicht deshalb zu beanstanden, weil der Beschwerdeführer früher einmal unter anderen Umständen von den Behörden eines anderen Kantons ausgeschafft werden konnte. Entscheidend sind einzig die aktuellen Umstände im vorliegenden Zusammenhang.
Solange die albanische Botschaft kein Reisepapier ausstellt, ist davon auszugehen, dass der Beschwerdeführer nicht nach Albanien eingelassen würde. Beweise für eine konstante gegenteilige Praxis gibt es nicht.
f) Schliesslich führt der Beschwerdeführer aus, er sei in die Schweiz gekommen, um ein Asylgesuch zu stellen.
Es ist unklar, ob er sich dabei auf seine erstmalige Einreise, die zum Asylentscheid vom 3. Mai 1999 führte, oder auf seine nachmalige Wiedereinreise bezieht, welche seine hier massgebliche Wegweisung zur Folge hatte. Ein erneutes Asylgesuch hat er, soweit bekannt, nicht gestellt. Im Übrigen würde nach der bundesgerichtlichen Rechtsprechung auch ein solches nicht zur Unzulässigkeit der Haft führen, nachdem mit einer Erledigung innert kurzer Frist gerechnet werden dürfte (vgl. <ref-ruling> E. 5 S. 384).
g) Ergänzend wird auf die Ausführungen im angefochtenen Entscheid sowie in der Vernehmlassung der Fremdenpolizei der Stadt Bern an das Bundesgericht verwiesen (Art. 36a Abs. 3 OG).
3.- a) Bei diesem Verfahrensausgang würde der Beschwerdeführer kostenpflichtig (Art. 156 Abs. 1 OG). Es rechtfertigt sich jedoch mit Blick auf seine finanziellen Verhältnisse, von der Erhebung einer Gerichtsgebühr abzusehen (Art. 153a Abs. 1 OG).
b) Die Fremdenpolizei der Stadt Bern wird ersucht, sicherzustellen, dass das vorliegende Urteil dem Beschwerdeführer korrekt eröffnet und verständlich gemacht wird.

Demnach erkennt das Bundesgericht
im Verfahren nach Art. 36a OG:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2.- Es werden keine Kosten erhoben.
3.- Dieses Urteil wird dem Beschwerdeführer, der Fremdenpolizei der Stadt Bern, dem Haftgericht III Bern-Mittelland und dem Eidgenössischen Justiz- und Polizeidepartement schriftlich mitgeteilt.
_
Lausanne, 25. April 2000
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: