Sachverhalt: A. X._ (geb. 1978) stammt aus der Republik Dagestan, Russland. Er heiratete am 19. Juli 2005 dort die Schweizer Bürgerin A._. Am 13. März 2006 reiste er in die Schweiz ein, am 17. März 2006 erhielt er gestützt auf das von der Ehefrau eingereichte Gesuch um Familiennachzug eine Aufenthaltsbewilligung der Migrationsbehörde des Kantons Basel-Stadt. Am 1. Februar 2007 kam die gemeinsame Tochter B._ zur Welt; sie verfügt als schweizerische Staatsangehörige über ein gefestigtes Anwesenheitsrecht. B. Nach einer längeren Abwesenheit von X._ ab dem Mai 2008 mit unbekanntem Aufenthaltsort beantragte seine Gattin das Getrenntleben; am 25. Juli 2008 entsprach das Zivilgericht Basel-Stadt dem Gesuch und übertrug ihr das Sorgerecht über die gemeinsame Tochter. Infolge der längeren Abwesenheit ohne Abmeldung strich die Migrationsbehörde X._ am 10. Dezember 2008 - rückwirkend auf den 10. Mai 2008 - amtlich aus der Aufenthaltskontrolle des Kantons Basel-Stadt. Zu einem unbekannten Zeitpunkt reiste X._ erneut in die Schweiz ein, bezog ab dem 21. Januar 2009 Sozialhilfe und ersuchte am 23. Januar 2009 um eine erneute Erteilung der Aufenthaltsbewilligung zum Verbleib bei der Gattin. Diese wurde ihm mit Verfügung vom 4. Juni 2010 verweigert; das Migrationsamt ordnete seine Wegweisung an. Mit Urteil vom 10. Januar 2011 wurde die Ehe zwischen X._ und A._ geschieden und die elterliche Sorge über B._ definitiv auf die Mutter übertragen. Einen Rekurs gegen die Nichterteilung der Aufenthaltsbewilligung und die Wegweisung wies das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt am 12. August 2011 ab. Dieser Entscheid wurde vom Appellationsgericht des Kantons Basel-Stadt mit Urteil vom 13. März 2012 bestätigt. C. X._ beantragt mit Eingabe vom 13. April 2012 dem Bundesgericht, den Entscheid der Vorinstanz aufzuheben; es sei ihm eine Aufenthaltsbewilligung zum Verbleib bei seiner Tochter zu erteilen, von einer Wegweisung sei abzusehen. Das Bundesgericht hat keine Vernehmlassungen eingeholt, wohl aber die kantonalen Akten beigezogen. D. Mit Verfügung vom 11. Mai 2012 wurde ein Gesuch von X._ um unentgeltliche Rechtspflege abgewiesen.