Sachverhalt:
A. A._ (geb. 1992) stammt aus der Türkei. Er reiste am 21. Juni 2011 in die Schweiz ein und stellte ein Asylgesuch. Das Bundesamt für Migration (BFM) hat dieses am 11. Oktober 2011 abgelehnt und A._ aus der Schweiz weggewiesen. Eine gegen den Wegweisungsentscheid gerichtete Beschwerde an das Bundesverwaltungsgericht blieb erfolglos (Urteil vom 14. Dezember 2011). Das BFM hatte A._ daraufhin eine Ausreisefrist bis zum 13. Januar 2012 gesetzt. Dieser reiste in der Folge unkontrolliert aus und lebte ohne Anwesenheitsberechtigung in X._ (Frankreich).
Gemäss den Feststellungen der Vorinstanz hat sich A._ mit der deutschen Staatsangehörigen B._ (geb. 1978) verlobt. Am 30. Juli 2012 hat B._ ein Gesuch um Familiennachzug zwecks Heirat gestellt. Das Verfahren betreffend Aufenthaltsbewilligung aufgrund beabsichtigter Eheschliessung soll gemäss den vorinstanzlichen Feststellungen nach wie vor hängig sein.
B. A._ ist zu einem unbestimmten Zeitpunkt ohne Visum und ohne Reisedokumente wieder in die Schweiz eingereist. Am 28. Januar 2013 ist er in Y._ (SO) von der Polizei festgenommen und dem Kanton Basel-Stadt zugeführt worden. Er stellte am 20. Februar 2012 erneut ein Asylgesuch, worauf das kantonale Migrationsamt am 30. Januar 2013 die Vorbereitungshaft verfügte. Diese wurde vom Einzelrichter für Zwangsmassnahmen im Ausländerrecht des Appellationsgerichts des Kantons Basel-Stadt am 1. Februar 2013 bis zum 28. März 2013 bestätigt.
Nachdem A._ sein Asylgesuch am 20. Februar 2013 zurückgezogen hatte, wies ihn das kantonale Migrationsamt gleichentags aus dem Schengen Raum weg. Es beantragte dem Einzelrichter für Zwangsmassnahmen im Ausländerrecht, die Vorbereitungshaft in eine Ausschaffungshaft umzuwandeln. Der Einzelrichter verweigerte die angeordnete Ausschaffungshaft, sah es jedoch als zulässig an, die ausländerrechtlich begründetet Festhaltung weiterhin und bis zum 19. April 2013 als Vorbereitungshaft zu bestätigen (Urteil vom 22. Februar 2013).
C. Mit Eingabe vom 4. März 2013 beantragt A._ dem Bundesgericht, die Urteile des Einzelrichters für Zwangsmassnahmen vom 1. und vom 22. Februar 2013 seien aufzuheben. Das Migrationsamt sei anzuweisen, ihn aus der Haft zu entlassen. Er macht geltend, sein Anspruch auf rechtliches Gehör sei verletzt worden, zudem bestehe kein Haftgrund und erweise sich seine Festhaltung wegen der bevorstehenden Ehe als unverhältnismässig. Ihm sei für das bundesgerichtliche Verfahren die unentgeltliche Prozessführung zu gewähren.
Mit Verfügung vom 5. März 2013 hat der Präsident der II. öffentlich-rechtlichen Abteilung das Gesuch um aufschiebende Wirkung (unverzügliche Haftentlassung) abgewiesen. Auf die Erhebung eines Kostenvorschusses wurde einstweilen verzichtet.

Erwägungen:
1. 1.1 Sowohl gegen den letztinstanzlichen Entscheid über die Anordnung der Ausschaffungshaft oder die Vorbereitungshaft als auch gegen jeden kantonal letztinstanzlichen Entscheid über die Haftverlängerung steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> an das Bundesgericht offen. Die vorliegende Beschwerde erweist sich daher als zulässig (Urteile 2C_1017/2012 vom 30. Oktober 2012 E. 1; 2C_413/2012 vom 22. Mai 2012 E. 1; 2D_66/2011 vom 13 Dezember 2011 E. 1).
1.2 Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden. Es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen oder sie mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (<ref-ruling> E. 1.4 S. 400).
2. 2.1 Um die Durchführung eines Wegweisungsverfahrens sicherzustellen, kann die zuständige kantonale Behörde eine ausländische Person, die keine Aufenthalts- oder Niederlassungsbewilligung besitzt, während der Vorbereitung des Entscheids über ihre Aufenthaltsberechtigung dann für höchstens sechs Monate in (Vorbereitungs-)Haft nehmen, wenn sie sich rechtswidrig in der Schweiz aufhält, ein Asylgesuch einreicht und damit offensichtlich bezweckt, den drohenden Vollzug einer Weg- oder Ausweisung zu vermeiden (Art. 75 Abs. 1 lit. f AuG). Dies wird von Gesetzes wegen vermutet, wenn ihm eine frühere Einreichung des Asylgesuchs möglich und zumutbar gewesen wäre und er sein Gesuch in einem engen zeitlichen Zusammenhang mit einer Verhaftung, einem Strafverfahren, dem Vollzug einer Strafe oder dem Erlass einer Wegweisungsverfügung stellt (Art. 75 Abs. 1 lit. f AuG). Diese Regelung ist in das Gesetz aufgenommen worden, um die Vorbereitungshaft mit dem asylrechtlichen Nichteintretensgrund der missbräuchlichen Nachreichung eines Asylgesuchs (<ref-law> [SR 142.31]) zu koordinieren (vgl. die Botschaft des Bundesrats vom 8. März 2002 zum Bundesgesetz über die Ausländerinnen und Ausländer, BBl 2002 S. 3709 ff., dort S. 3816; Urteil 2C_275/2007 vom 4. September 2007 E. 2.1; ANDREAS ZÜND, in: Spescha/Thür/Zünd/Bolzli [Hrsg.], Migrationsrecht, 3. Aufl. 2012, N. 9 zu Art. 75; THOMAS HUGI YAR, Zwangsmassnahmen im Ausländerrecht, in: Uebersax/Rudin/Hugi Yar/Geiser [Hrsg.], Ausländerrecht, 2. Aufl. 2009, N. 10.67).
2.2 Wurde bereits ein erstinstanzlicher Weg- oder Ausweisungsentscheid eröffnet, kann die zuständige Behörde den betroffenen Ausländer zur Sicherstellung von dessen Vollzug unter anderem in ausländerrechtlicher Festhaltung (Ausschaffungshaft) belassen, wenn er sich bereits in Vorbereitungshaft gestützt auf Art. 75 AuG befindet (Art. 76 Abs. 1 lit. a AuG). Der Wegweisungsentscheid muss dabei nicht bereits rechtskräftig sein; es genügt, dass sein Vollzug (z.B. wegen fehlender Papiere) noch nicht möglich, jedoch absehbar erscheint (vgl. allgemein zur Ausschaffungshaft <ref-ruling> ff., 377 ff.; <ref-ruling> ff.; Urteile 2C_1017/2012 vom 30. Oktober 2012 E. 4; 2C_749/2012 vom 28. August 2012 E. 1; 2C_332/2012 vom 3. Mai 2012 E. 1).
2.3 Die Vorbereitungshaft wie die Ausschaffungshaft setzen grundsätzlich die rechtliche und tatsächliche Durchführbarkeit der bezweckten bzw. angeordneten Entfernungsmassnahme voraus (vgl. Art. 80 Abs. 6 lit. a AuG; Urteile 2C_168/2013 vom 7. März 2013 E. 1.3.2; 2C_749/2012 vom 28. August 2012 E. 1; 2C_1150/2012 vom 7. Dezember 2012 E. 2.1); die Vorbereitung des Entscheids bzw. der Vollzug der Entfernungsmassnahme muss mit dem nötigen Nachdruck verfolgt werden (Art. 75 Abs. 2 bzw. 76 Abs. 4 AuG: "Beschleunigungsgebot"; Urteile 2C_1150/2012 vom 7. Dezember 2012 E. 2.1; 2C_749/2012 vom 28. August 2012 E. 1) und die Haftdauer muss den Umständen des Einzelfalls angemessen sein (vgl. Art. 10 Abs. 2 und Art. 36 Abs. 3 BV; vgl. das Urteil des EGMR Jusic gegen Schweiz vom 2. Dezember 2010 [Nr. 4691/06], §§ 67 ff., insbesondere § 73; HUGI YAR, a.a.O., N. 10.114 ff.). Dabei sind die Tragweite des Beschleunigungsgebots, die Komplexität des Falles unter Einschluss der Frage der Durchführbarkeit der Ausschaffung sowie die Möglichkeit des Inhaftierten zu berücksichtigen, allenfalls mehrmals ein Haftentlassungsgesuch stellen zu können. Es ist jeweils im Einzelfall zu prüfen, ob die verfügte Haft bzw. deren Dauer erforderlich ist und nicht gegen das Übermassverbot, d.h. das sachgerechte und zumutbare Verhältnis von Mittel (die Haft) und Zweck, verstösst (vgl. <ref-ruling> E. 5.1 S. 5 und unpublizierte E. 7; <ref-ruling> ff. [zur Ausschaffungshaft]; <ref-ruling> E. 2.3.2 S. 97; <ref-ruling> E. 2.2 S. 100 [zur Durchsetzungshaft]; Urteil 2C_275/2007 vom 4. September 2007 E. 2.3 [zur Vorbereitungshaft]; HUGI YAR, a.a.O., N. 10.114 ff.).
3. Der Beschwerdeführer bringt vor, die durch den Haftrichter am 1. und 22. Februar 2013 genehmigte Vorbereitungshaft sei unzulässig. Weder sei der im vorinstanzlichen Urteil angegebene Haftgrund erfüllt noch erweise sich eine ausländerrechtliche Festhaltung als verhältnismässig.
3.1 Entgegen der Auffassung des Beschwerdeführers war die Genehmigung der Vorbereitungshaft durch den Einzelrichter am 1. Februar 2013 nicht zum Vornherein unzulässig: Der Beschwerdeführer reiste illegal in die Schweiz ein und verfügte zu keinem Zeitpunkt über eine Aufenthalts- oder Niederlassungsbewilligung. Kurz nach seiner Festnahme durch die Polizei am 28. Januar 2013 stellte er ein neuerliches Asylgesuch, worauf das Migrationsamt Basel-Stadt die Vorbereitungshaft verfügte. Der Beschwerdeführer räumt selbst ein, das Asylgesuch eingereicht zu haben, um einen legalen Status für die geplante Eheschliessung zu erlangen. Wenn die Vorinstanz demnach eine Inhaftierung (Vorbereitungshaft) gestützt auf Art. 75 Abs. 1 lit. f. bestätigt hat, um den mutmasslich mit der (missbräuchlichen) Nachreichung des Asylgesuchs verbundenen Nichteintretens- und Wegweisungsentscheids sicherstellen zu können, ist dies nicht zum Vornherein bundesrechtswidrig. Das Wegweisungsverfahren durfte am 1. Februar 2013 grundsätzlich mit der Vorbereitungshaft sichergestellt werden (zur Frage der Verhältnismässigkeit der ausländerrechtlichen Haft im vorliegenden Fall vgl. unten E. 5).
3.2 Fraglich ist, ob auch die zweite, am 22. Februar 2013 vom Einzelrichter bestätigte Vorbereitungshaft rechtens war.
3.2.1 Der Beschwerdeführer zog das unmittelbar nach seiner Verhaftung in Dornach gestellte Asylgesuch am 20. Februar 2013 zurück. Das Migrationsamt wies ihn mit Verfügung vom gleichen Tag wegen Einreise ohne gültige Reisedokumente und ohne gültiges Visum aus dem Schengenraum weg und beantragte der Vorinstanz die Ausschaffungshaft. Die Vorinstanz sah die vom Migrationsamt beantragte Ausschaffungshaft als unzulässig an und wandelte sie um in die Weiterführung der bereits bestehenden Vorbereitungshaft. Sie begründete dies damit, dass infolge des am 30. Juli 2012 eingereichten Gesuchs um Kurzaufenthalt zwecks Heirat bzw. Gesuch um Familiennachzug gemäss dem Abkommen vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit (FZA; SR 0.632.31) nicht auf einen "bereits ergangenen Wegweisungsentscheid allein" abgestellt werden dürfe. Es werde "immer noch ein Entscheid über die Aufenthaltsberechtigung vorbereitet", sodass die "Vorschriften über die Vorbereitungshaft anzuwenden" seien.
3.2.2 Das Verfahren vor dem Haftrichter dient nicht der Überprüfung des Wegweisungsentscheids oder von anderen den Ausländer zur Ausreise verpflichtenden Verfügungen. Der Haftrichter hat sich grundsätzlich nur zu vergewissern, ob (überhaupt) ein Weg- oder Ausweisungsentscheid vorliegt; dessen Rechtmässigkeit bildet nicht Gegenstand seines Verfahrens. Diesbezügliche Einwände sind im Asyl-, Bewilligungs- oder Wegweisungsverfahren durch die jeweils zuständigen Behörden zu prüfen, nicht (erstinstanzlich) durch den Haftrichter (vgl. die Urteile 2C_168/2013 vom 7. März 2013 E. 1.3.1; 2C_749/2012 vom 28. August 2012 E. 2.1; 2C_304/2012 vom 1. Mai 2012 E. 2.1 und 2C_455/2009 vom 5. August 2009 E. 2.3). Die betroffene Person muss sich in diesen Punkten nötigenfalls mit einem Wiedererwägungsgesuch an das Bundesamt oder die zuständige kantonale Ausländerbehörde wenden und hernach den entsprechenden Rechtsweg beschreiten (vgl. <ref-ruling> E. 2 S. 221; TARKAN GÖKSU, in: Caroni/Gächter/Thurnherr [Hrsg.], Bundesgesetz über die Ausländerinnen und Ausländer [AuG], 2010, N. 14 zu Art. 80; ZÜND, a.a.O., N. 6 f. zu Art. 80 AuG [e contrario]; HUGI YAR, a.a.O., N. 10.28). Nur wenn der Wegweisungsentscheid offensichtlich unzulässig, d.h. geradezu willkürlich bzw. nichtig erscheint, darf bzw. muss die Haftgenehmigung verweigert werden, da der Vollzug einer offenkundig rechtswidrigen Anordnung nicht mit einer ausländerrechtlichen Zwangsmassnahme sichergestellt werden kann (BGE <ref-ruling> E. 2 S. 58; <ref-ruling> E. 2.2.2 S. 198 mit Hinweisen; <ref-ruling> E. 2c S. 62; Urteil 2C_749/2012 vom 28. August 2012 E. 2.1).
3.2.3 Das Migrationsamt hatte die Wegweisung des Beschwerdeführers gestützt auf Art. 64 Abs. 1 lit. a AuG verfügt, weil der Beschwerdeführer ohne gültige Einreisedokumente, sowie ohne Visum bzw. gültigen Aufenthaltstitel eingereist war. Der Wegweisungsentscheid wurde angefochten; den Akten lässt sich nicht entnehmen, ob dieser bereits rechtskräftig bestätigt wurde. Vom Vorliegen eines Wegweisungsentscheids, der offensichtlich unrichtig wäre, ist demnach nicht auszugehen (BGE <ref-ruling> E. 2 S. 58; <ref-ruling> E. 2.2.2 S. 198 mit Hinweisen; <ref-ruling> E. 2c S. 62). Dass es sich hierbei um einen Wegweisungsentscheid handelt, der möglicherweise noch nicht in Rechtskraft erwachsen ist, vermag daran nichts zu ändern (vgl. oben E. 2.2). Im Übrigen liegt auch keine offensichtliche Unzulässigkeit der verfügten Wegweisung infolge mangelnder Zuständigkeit vor: Die Wegweisungsverfügung erfolgte entgegen der Ansicht des Beschwerdeführers nicht direkt von der Asyl-, sondern von der kantonalen Migrationsbehörde nach dem Rückzug des Asylgesuchs, was grundsätzlich zulässig war (Art. 64 Abs. 1 AuG). Ebenso wenig steht die Hängigkeit eines Bewilligungsverfahrens der Wegweisung grundsätzlich entgegen (vgl. Art. 17 AuG; vgl. hierzu auch unten E. 5.2).
3.2.4 Es ist somit vom Vorliegen eines Wegweisungsentscheids auszugehen, der nicht offensichtlich unrichtig oder willkürlich ist. Wenn ein im Rahmen der (zurückhaltenden) Haftprüfung zulässiger Wegweisungsentscheid vorliegt, kann jedoch die ausländerrechtliche Zwangsmassnahme nicht mehr der Sicherung des Wegweisungsverfahrens dienen, wie dies Art. 75 AuG (Vorbereitungshaft) vorsieht. Die Voraussetzungen der Vorbereitungshaft nach Art. 75 Abs. 1 lit. f AuG waren zum Zeitpunkt des zweiten haftrichterlichen Genehmigungsentscheids am 22. Februar 2012 nicht (mehr) gegeben. Die Umwandlung der beantragten Ausschaffungshaft in eine Weiterführung der Vorbereitungshaft durch die Vorinstanz am 22. Februar 2013 war demnach unzulässig.
4. 4.1 Gemäss Art. 76 Abs. 1 lit. a AuG sind die Haftgründe, die Art. 75 AuG für die Anordnung der Vorbereitungshaft vorsieht, auch als Gründe für die Ausschaffungshaft zulässig, sofern sich die ausländische Person bereits in Vorbereitungshaft befindet. Die vorliegend angefochtene Festhaltung ist deshalb materiellrechtlich gestützt auf Art. 76 AuG nicht zum Vornherein bundesrechtswidrig: Der Haftrichter hat zwar die falsche Rechtsgrundlage geprüft und deren Voraussetzungen als gegeben erachtet; die beanstandete ausländerrechtliche Festhaltung könnte aber als Ausschaffungshaft rechtens sein. Das Bundesgericht kann im Falle der materiellen Rechtmässigkeit eine unzutreffende Begründung durch eine eigene, bundesrechtskonforme ersetzen und den angefochtenen Entscheid mit dieser bestätigen ("Begründungssubstitution", vgl. <ref-ruling> E. 2.2 S. 550; Urteile 2C_131/2011 vom 25. Februar 2012 E. 3.2.3; 2C_963/2010 vom 11. Januar 2011 E. 2.3.3 und 2C_945/2010 vom 5. Januar 2011 E. 2.3).
4.2 Der Beschwerdeführer sieht in der vom Haftrichter bestätigten Vorbereitungshaft allerdings eine Gehörsverletzung (<ref-law>): Der Einzelrichter habe ihn zur am 22. Februar 2013 genehmigten Verlängerung der Vorbereitungshaft nicht angehört. Da die kantonale Migrationsbehörde die Ausschaffungshaft und (auch eventualiter) nicht die Vorbereitungshaft beantragt hatte, habe er sich zur Unzulässigkeit derselben nicht äussern können. Tatsächlich bestand für den Beschwerdeführer zum Zeitpunkt der Haftverhandlung keine Möglichkeit und auch kein Anlass, sich zur Fortsetzung der Vorbereitungshaft zu äussern. Allerdings geht seine Rüge fehl, wonach der Haftgrund für die Vorbereitungshaft (Art. 75 Abs. 1 lit. f AuG) nicht auch unter dem Titel der Ausschaffungshaft gegeben sein könne (vgl. Art. 76 Abs. 1 lit.a AuG). Eine Gehörsverletzung könnte somit nur - aber immerhin - die übrigen Voraussetzungen für die Anordnung der Vorbereitungshaft betreffen, denn zur Ausschaffungshaft konnte er sich angesichts des Haftantrags des Migrationsamts bereits äussern. Der Beschwerdeführer konnte hiernach, im bundesgerichtlichen Verfahren, zur Vorbereitungshaft Stellung nehmen. Inwiefern eine Gehörsverletzung im ausländerrechtlichen Haftverfahren vorliegt bzw. überhaupt heilbar ist, kann vorliegend offenbleiben, da die Beschwerde aus anderen Gründen ohnehin gutzuheissen ist (E. 5).
5. Da die Voraussetzungen für eine Inhaftierung nach Art. 75 Abs. 1 lit. f AuG zum Zeitpunkt des ersten haftrichterlichen Urteils grundsätzlich gegeben waren (oben E. 3.1) und mittlerweile ein im Rahmen der Haftüberprüfung verbindlicher Wegweisungsentscheid vorliegt (E. 3.2), sind auch die Voraussetzungen, den Beschwerdeführer in Ausschaffungshaft zu nehmen, grundsätzlich erfüllt (Art. 76 Abs. 1 lit. a AuG; oben E. 4.1). Zu prüfen bleibt jedoch, ob die zu Unrecht als Vorbereitungshaft bezeichnete Festhaltung auch unter den weiteren Voraussetzungen als Ausschaffungshaft zulässig wäre, d.h. insbesondere, ob sie sich als verhältnismässig erweist (vgl. oben E. 2.1).
5.1 Die ausländerrechtlich begründete Haft muss verhältnismässig, d.h. zweckbezogen auf die Sicherung des Vollzugs der Entfernungsmassnahme ausgerichtet sein; es muss jeweils aufgrund sämtlicher Umstände geklärt werden, ob sie (noch) geeignet bzw. erforderlich erscheint und nicht gegen das Übermassverbot, d.h. das sachgerechte und zumutbare Verhältnis von Mittel und Zweck, verstösst (<ref-ruling> E. 5.1 S. 5 und unpublizierte E. 7; BGE <ref-ruling> ff. [zur Ausschaffungshaft]; <ref-ruling> E. 2.3.2 S. 97; <ref-ruling> E. 2.2 S. 100 [zur Durchsetzungshaft]). Die entsprechenden Anforderungen an die ausländerrechtliche Festhaltung ergeben sich aus dem Haftzweck, aus Art. 5 Ziff. 1 lit. f EMRK und dem Verhältnismässigkeitsgrundsatz (Art. 5 Abs. 2 und Art. 36 Abs. 3 i.V.m. <ref-law>), aber auch aus der für die Schweiz im Rahmen des Schengen-Besitzstands relevanten sog. "Rückführungsrichtlinie" (Richtlinie 2008/115/EG des Europäischen Parlaments und des Rats vom 16. Dezember 2008 über gemeinsame Normen und Verfahren in den Mitgliedstaaten zur Rückführung illegal aufhältiger Drittstaatsangehöriger, ABl. L 348 vom 24. Dezember 2008 S. 98 ff.; vgl. ANDRÉ EQUEY, Änderungen im Bereich der Zwangsmassnahmen im Ausländerrecht aufgrund der Übernahme der EG-Rückführungsrichtlinie durch die Schweiz, AJP 2011 S. 924 ff., dort S. 934): Zwangsmassnahmen zur Durchführung der Abschiebung von Widerstand leistenden Drittstaatsangehörigen dürfen nicht über die Grenzen des Erforderlichen hinausgehen (Subsidiaritätsgrundsatz). Sie müssen nach dem einzelstaatlichen Recht im Einklang mit den Grundrechten und unter gebührender Berücksichtigung der Menschenwürde und körperlichen Unversehrtheit der betroffenen Personen erfolgen (Art. 8 Abs. 4 RL 2008/115/EG). Die Haftdauer hat so kurz wie möglich zu sein; sie darf sich nur auf die Dauer der laufenden Abschiebungsvorkehrungen erstrecken, soweit diese mit der gebotenen Sorgfalt vorangetrieben werden (vgl. Art. 15 Abs. 1 RL 2008/115/EG). Als mildere Zwangsmassnahmen nennt die Richtlinie eine regelmässige Meldepflicht bei den Behörden, die Hinterlegung einer angemessenen Sicherheit, das Einreichen von Papieren und die Verpflichtung, sich an einem bestimmten Ort aufzuhalten (Art. 7 Abs. 3 RL 2008/115/EG; EQUEY, a.a.O., S. 936).
5.2 Vorliegend wurde die Wegweisung verfügt; vor dem Hintergrund eines bevorstehenden Wegweisungsvollzugs und dem vor zwei Jahren bereits gestellten und abgewiesenen Asylgesuch und seiner Wiedereinreise könnte sich eine ausländerrechtliche Zwangsmassnahme zur Sicherung der Wegweisung rechtfertigen. Allerdings bringt der Beschwerdeführer vor, er stehe kurz vor der Heirat mit der deutschen Staatsangehörigen B._. Indem der Beschwerdeführer in vertretbarer Weise einen Anspruch nach Art. 8 EMRK bzw. nach FZA geltend macht (geplante Heirat mit einer deutschen Staatsbürgerin), vermochte seine erneute Einreichung eines Asylgesuchs nach seiner Verhaftung am 28. Januar 2013 in Dornach (das später, unmittelbar vor der Wegweisungsverfügung wieder zurückgezogen wurde) die hängigen aufenthaltsrechtlichen Bewilligungsverfahren nicht zum Erlöschen zu bringen: Grundsätzlich werden fremdenpolizeiliche Verfahren zwar mit dem Einreichen eines Asylgesuchs gegenstandslos (<ref-law>); vorbehalten bleiben jedoch fremdenpolizeiliche Verfahren betreffend die Erteilung von Aufenthaltsbewilligungen, wenn nach der bundesgerichtlichen Praxis hierauf ein Anspruch besteht (vgl. Botschaft zur Totalrevision des Asylgesetzes ..., BBl 1996 II 1 ff. Ziff. 21.021; vgl. zu <ref-law> Urteil 2C_702/2011 vom 23. Februar 2012 E. 3.3.2 in fine).
Allerdings stehen auch Heiratspläne einer ausländerrechtlichen Festhaltung grundsätzlich nicht entgegen (vgl. Urteil 2C_150/2012 vom 14. Februar 2012 E. 2.2.2); anders ist dies, wenn sämtliche notwendigen Papiere vorliegen, ein Heiratstermin feststeht und binnen kurzer Frist mit der Erteilung einer Aufenthaltsberechtigung zu rechnen ist (Urteile 2C_150/2012 vom 14. Februar 2012 E. 2.2.2; 2C_958/2010 vom 6. Januar 2011 E. 2.3 und 2C_756/2009 vom 15. Dezember 2009 E. 2.3.2 mit Hinweisen). Gemäss den vorinstanzlichen Feststellungen liegt ein Schreiben des Zivilstandsamtes Basel-Stadt vom 17. Januar 2013 vor, wonach alle für die Verheiratung mit der deutschen Staatsbürgerin B._ notwendigen Dokumente, mit Ausnahme der Bescheinigung über den legalen Aufenthalt, vorliegen würden. Der Beschwerdeführer kann als künftiger Ehepartner einer gestützt auf das Freizügigkeitsabkommen in der Schweiz anwesenheitsberechtigten Person einen (abgeleiteten) Aufenthaltsanspruch nach Art. 3 Anhang I FZA geltend machen. Dass sich der Beschwerdeführer hierfür bereits rechtmässig mit einem nicht nur vorübergehenden Aufenthaltstitel in der Schweiz oder in einem anderen Vertragsstaat aufgehalten haben muss, ist gemäss der Rechtsprechung nicht erforderlich (<ref-ruling> E. 3 S. 11 ff.; EuGH-Urteil C-127/08 vom 25. Juli 2008 i.S. Metock et al.). Vor diesem Hintergrund ist davon auszugehen, dass er sich den Behörden zur Verfügung halten wird, um die Durchführung des Bewilligungsverfahrens nicht zu gefährden.
Das Migrationsamt scheint in seiner Vernehmlassung vom 11. März 2013 gewisse Zweifel an der Echtheit des Ehewillens des Beschwerdeführers durchblicken zu lassen. Ob sich die Hinweise bestätigen, wird von den hierfür zuständigen Behörden im Rahmen des Bewilligungsverfahrens zu entscheiden sein, ebenso wie die Frage, ob der Beschwerdeführer das Bewilligungsverfahren im Ausland abzuwarten hat, oder in der Schweiz verbleiben kann (vgl. Art. 17 Abs. 1 und 2 AuG; <ref-law>; EGMR-Urteils O'Donoghue u. Mitb. gegen Vereinigtes Königreich vom 14. Dezember 2010 [Nr. 34848/07] <ref-ruling> E. 3.5 und 3.7 S. 356 ff.; 359 f.; Urteil 2C_702/2011 vom 23. Februar 2012 E. 4.3; 2C_195/2012 vom 2. Januar 2013 E. 2 und E. 3).
5.3 Die ausländerrechtliche Haft des Beschwerdeführers hat bei einer Auslegung von Art. 76 und Art. 80 AuG im Lichte der Vorgaben der Rückführungsrichtlinie und von Art. 5 Ziff. 1 lit. f und Art. 8 EMRK als nicht erforderlich und daher als unverhältnismässig zu gelten: Er steht unmittelbar vor der Heirat mit einer anwesenheitsberechtigten deutschen Staatsbürgerin und sein Gesuch um Aufenthaltsbewilligung zwecks Heirat ist seit längerer Zeit hängig. Auch ist nicht ersichtlich, ob der Wegweisungsentscheid rechtskräftig bestätigt wurde (vgl. E. 3.2.3), sodass es nach wie vor nicht ausgeschlossen ist, dass der Beschwerdeführer das Verfahren allenfalls sogar in der Schweiz wird abwarten können (Art. 17 Abs. 2 AuG). Es ist demnach davon auszugehen, dass er sich - selbst im Falle, dass er das Verfahren im Ausland abwarten müsste - den Behörden zur Verfügung halten wird. Der Haftzweck kann demnach auch mit milderen Mitteln (E. 6) erreicht werden. Es erübrigt sich damit, die weiteren vorgebrachten Rügen zu prüfen.
6. Der Beschwerdeführer ist aus der Haft zu entlassen. Unbenommen ist es der Behörde, ihm gegenüber mildere Massnahmen wie die Meldepflicht (Art. 64e lit. a AuG) oder allenfalls gar - falls ein rechtskräftiger Wegweisungsentscheid vorliegt - eine Eingrenzung anzuordnen (Art. 74 Abs. 1 lit. b AuG). Zweck dieser Massnahme ist es, den Verbleib der ausländischen Person zu kontrollieren sowie ihre Verfügbarkeit für die Vorbereitung und Durchführung der Wegweisung weiterhin sicherzustellen (vgl. zur Eingrenzung auch die Urteile 2C_1044/2012 vom 5. November 2012; 2C_1089/2012 vom 22. November 2012 E. 5; ZÜND, a.a.O., N. 5 zu Art. 74 AuG; zur Meldepflicht vgl. MARC SPESCHA, in: Spescha/Thür/Zünd/Bolzli; Migrationsrecht, 3. Aufl. 2012, N. 1 zu Art. 64e).
7. 7.1 Die Beschwerde ist demnach gutzuheissen, die angefochtenen Entscheide des Appellationsgerichts des Kantons Basel-Stadt als Verwaltungsgericht, Einzelrichter für Zwangsmassnahmen im Ausländerrecht, sind aufzuheben.
7.2 Dem Verfahrensausgang entsprechend werden keine Kosten erhoben (Art. 66 Abs. 1 und 4 BGG). Der Kanton Basel-Stadt wird entschädigungspflichtig (<ref-law>). Damit wird das Gesuch um unentgeltliche Rechtspflege und Verbeiständung gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und die Urteile des Appellationsgerichts des Kantons Basel-Stadt als Verwaltungsgericht, Einzelrichter für Zwangsmassnahmen im Ausländerrecht, vom 1. und 22. Februar 2013 werden aufgehoben. Der Beschwerdeführer ist unverzüglich aus der Haft zu entlassen.
2. 2.1 Es werden keine Kosten erhoben.
2.2 Der Kanton Basel-Stadt hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
2.3 Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird als gegenstandslos abgeschrieben.
3. Dieses Urteil wird den Verfahrensbeteiligten, dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht, Einzelrichter für Zwangsmassnahmen im Ausländerrecht, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 26. März 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Hänni