in Erwägung gezogen:
1.-M._ reiste am 7. Mai 2000 illegal in die Schweiz ein und stellte ein Asylgesuch. Er gab an, am 19.
Februar 1983 geboren worden zu sein und aus Marokko zu stammen. Dabei wies er sich mit einer entsprechenden Geburtsurkunde aus. Eine Knochenalter-Bestimmung, durchgeführt im Bürgerspital Solothurn, ergab am 2. Juni 2000 für ihn ein Knochenalter von 16 Jahren (mit einer Standard-Deviation von +/- 12,8 Monaten). Am 16. März 2001 lehnte das Bundesamt für Flüchtlinge sein Asylgesuch ab und wies ihn aus der Schweiz weg; auf eine gegen diese Verfügung gerichtete Beschwerde trat die Schweizerische Asylrekurskommission am 19. April 2001 nicht ein.
In der Zwischenzeit ergingen gegen M._ verschiedene Strafverfügungen (u.a. wegen Ladendiebstählen, Entwendung eines Personenwagens zum Gebrauch, Besitzes von Kokain und Haschisch und wegen mehrfacher Widerhandlung gegen das Transportgesetz) der Jugendanwaltschaft des Kantons Solothurn, die jeweils unbedingte Einschliessungsstrafen anordnete. Am 1. April 2001 verschwand M._ aus der Unterkunft in Oberdorf, später wurde er im Fahndungssystem RIPOL zwecks Ausschaffung ausgeschrieben. Am 15. Juni 2001 erschien er auf dem Asylbüro des Amtes für öffentliche Sicherheit, um sich nach einer Möglichkeit zum Verbleib in der Schweiz zu erkundigen. Gleichentags nahm ihn das Amt (als Fremdenpolizeibehörde des Kantons Solothurn) in Ausschaffungshaft.
Am 18. Juni 2001 prüfte und bestätigte das Verwaltungsgericht des Kantons Solothurn die Ausschaffungshaft bis zum 14. September 2001.
Am 21. Juni 2001 meldete sich M._ aus der Haft beim Amt für öffentliche Sicherheit und gab an, seine wahre Identität nennen zu wollen. In einem Schliessfach, dessen Schlüssel M._ in der Unterkunft in Oberdorf versteckt hatte, fanden die Behörden in der Folge eine Reisetasche mit persönlichen Effekten und Dokumenten, darunter eine "Aufenthaltsgestattung" vom 3. April 2001 (gültig bis zum 3. Juli 2001), ausgestellt in Karlsruhe (Deutschland) auf den Namen "L._" (von Algerien), geboren 1985.
Gegen den Haftprüfungsentscheid vom 18. Juni 2001 hat M._ mit einer in französischer Sprache verfassten Eingabe vom 29. Juni 2001 beim Bundesgericht Beschwerde erhoben. Er macht geltend, sein Name sei in Wirklichkeit L._, geboren 1985, und er stamme aus Algerien. Er habe eine Adresse in Deutschland, wo er sich aufhalten könne ("que mon asyle est encore valable") und wohin er zurückkehren wolle.
Das Amt für öffentliche Sicherheit und das Verwaltungsgericht des Kantons Solothurn beantragen, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Das Bundesamt für Ausländerfragen hat sich innert Frist nicht geäussert. Der Beschwerdeführer hat von der Möglichkeit, sich ergänzend vernehmen zu lassen, nicht Gebrauch gemacht.
2.-a) Die zuständige kantonale Behörde kann einen Ausländer in Ausschaffungshaft nehmen bzw. in dieser belassen, sofern die Voraussetzungen von Art. 13b des Bundesgesetzes über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142. 20; in der Fassung des Bundesgesetzes vom 18. März 1994 über Zwangsmassnahmen im Ausländerrecht [Zwangsmassnahmengesetz; AS 1995 146 ff.]) erfüllt sind.
Danach ist erforderlich, dass ein erstinstanzlicher, nicht notwendigerweise auch rechtskräftiger Weg- oder Ausweisungsentscheid vorliegt (vgl. <ref-ruling> E. 2 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. 3a S. 374, 377 E. 2a S. 379). Zudem muss einer der in Art. 13b Abs. 1 ANAG genannten Haftgründe bestehen (<ref-ruling> E. 3a S. 374, 377 E. 3a S. 381; <ref-ruling> E. 1 S. 3), die Ausschaffung rechtlich und tatsächlich möglich sein (vgl. Art. 13c Abs. 5 lit. a ANAG; dazu <ref-ruling> E. 2 S. 220), und es sind die für den Vollzug der Wegweisung notwendigen Vorkehrungen umgehend zu treffen (Art. 13b Abs. 3 ANAG, Beschleunigungsgebot; vgl. <ref-ruling> ff.). Die Haft darf - vorerst - für höchstens drei Monate angeordnet werden (Art. 13b Abs. 2 ANAG).
b) Gegen den Beschwerdeführer liegt eine rechtskräftige Wegweisung vor; die gegen ihn angeordnete Ausschaffungshaft dient zur Sicherstellung von deren Vollzug, der (wegen der Ungewissheit über die Identität des Beschwerdeführers und wegen Fehlens von Reisepapieren) noch nicht möglich ist, wobei aber keine Anzeichen dafür bestehen, dass er nicht doch in absehbarer Zeit bewerkstelligt werden könnte.
Die hierfür notwendigen Vorkehrungen sind jedenfalls umgehend in die Wege geleitet worden; seit M._ ganz andere Angaben zu seiner Identität macht, werden auch die deutschen Behörden um Unterstützung gebeten.
c) Dass der Beschwerdeführer heute vermutlich erst 17 Jahre alt (vgl. Knochenalter-Bestimmung vom 2. Juni 2000) und damit noch minderjährig ist, steht der Anordnung von Ausschaffungshaft nicht entgegen (vgl. Art. 13c Abs. 3 ANAG), und es liegt auch kein Fall vor, in dem das Verwaltungsgericht bei der Haftprüfung dem minderjährigen Beschwerdeführer auf Grund der konkreten Umstände von Amtes wegen einen Rechtsbeistand hätte beigeben müssen (unveröffentlichtes Urteil vom 21. Juli 1999 i.S. P._, E. 2).
Seine Betreuung während der Dauer des Asylverfahrens wurde im Übrigen durch den Beizug einer Vertrauensperson sichergestellt (vgl. Anhörungsprotokoll vom 5. Juli 2000, S. 11).
Zu prüfen bleibt, ob der von den kantonalen Behörden geltend gemachte Haftgrund von Art. 13b Abs. 1 lit. c ANAG erfüllt ist.
d) Gemäss Art. 13b Abs. 1 lit. c ANAG ist die Ausschaffungshaft zulässig, wenn konkrete Anzeichen befürchten lassen, dass der Ausländer sich der Ausschaffung entziehen will, insbesondere weil sein bisheriges Verhalten darauf schliessen lässt, dass er sich behördlichen Anordnungen widersetzt (Untertauchensgefahr). Dabei muss der Vollzug der Wegweisung erheblich gefährdet erscheinen. Dies trifft namentlich zu, 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 (vgl.
<ref-ruling> E. 2a; <ref-ruling> E. 2b S. 198). Dies ist vorliegend der Fall: Um Reisepapiere hatte sich der Beschwerdeführer nicht bemüht, sondern im Gegenteil wiederholt zu Protokoll gegeben, nie in sein Heimatland zurückkehren zu wollen. In der Schweiz hatte er mehrfach delinquiert und wurde deswegen wiederholt zu unbedingten Einschliessungsstrafen verurteilt.
Sodann ist der Beschwerdeführer bereits einmal untergetaucht (vgl. E. 1). Als er wieder auf dem Asylbüro in Solothurn erschien, gab er an, er sei am 1. April 2001 nach Italien ausgereist. Vor dem Verwaltungsgericht sagte er drei Tage später aus, er habe gelogen, er sei nicht in Italien gewesen. Vielmehr habe er bei einer Frau gelebt, die er nun heiraten möchte. Für die Beschaffung der erforderlichen Dokumente habe er bereits nach Marokko geschrieben.
Als Heimatland gibt der Beschwerdeführer den schweizerischen Behörden gegenüber seit dem 21. Juni 2001 aber nicht mehr Marokko, sondern Algerien an, wobei keineswegs gesichert ist, dass die gemachten Angaben zu Herkunft und Identität nun der Wahrheit entsprechen. Unter diesen Umständen aber bestehen ernsthafte Anzeichen dafür, dass der Beschwerdeführer, sollte er aus der Haft entlassen werden, sich den Behörden für nähere Abklärungen und die Ausschaffung nicht zur Verfügung halten würde. Der Vollzug der Wegweisung erscheint erheblich gefährdet, und der Haftgrund von Art. 13b Abs. 1 lit. c ANAG ist klarerweise erfüllt (vgl. <ref-ruling> E. 2a S. 50 f.).
Die Bereitschaft des Beschwerdeführers, nach Deutschland ausreisen zu wollen ("envoyez-moi en Allemagne", vgl. S. 2 der Beschwerdeschrift), ändert am Gesagten nichts.
Diese Behauptung erscheint im Lichte seiner früheren, ebenso widersprüchlichen Aussagen ("Ich möchte unbedingt in der Schweiz bleiben"; "Wenn Sie mich frei lassen, gehe ich nach Italien zurück", vgl. S. 2 des angefochtenen Entscheides) unglaubwürdig. Im Übrigen muss eine allfällige Rückübernahme zuerst mit den deutschen Behörden abgesprochen werden. Wie erwähnt (E. 2b), sind die entsprechenden Abklärungen zur Zeit im Gange.
e) Die Verwaltungsgerichtsbeschwerde erweist sich damit als offensichtlich unbegründet, und sie ist - im vereinfachten Verfahren (Art. 36a OG) - abzuweisen.
3.-Entsprechend dem Ausgang würde der Beschwerdeführer für das bundesgerichtliche Verfahren an sich kostenpflichtig (Art. 156 OG). In Fällen der vorliegenden Art (dem Beschwerdeführer fehlen offensichtlich jegliche finanziellen Mittel) rechtfertigt es sich jedoch, von der Erhebung einer Gerichtsgebühr abzusehen (vgl. Art. 154 OG).

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, dem Amt für öffentliche Sicherheit (Ausländerfragen) und dem Verwaltungsgericht des Kantons Solothurn sowie dem Bundesamt für Ausländerfragen schriftlich mitgeteilt.
_
Lausanne, 17. Juli 2001
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: