Fatti: A. A._ (1976), cittadino del Mali, ha presentato una prima domanda d'asilo in Svizzera nel 2012, la quale è stata respinta il 5 aprile 2013 dall'allora Ufficio federale della migrazione (diventato poi la Segreteria di Stato della migrazione SEM), con una decisione di non entrata in materia. Una seconda domanda, depositata dopo che A._ ha cercato invano di ottenere l'asilo in Germania nel 2013, è stata ugualmente evasa con una decisione di non entrata in materia il 24 gennaio 2014. Del suo allontanamento è stato incaricato il Cantone Ticino. Durante il suo soggiorno in Svizzera A._ è stato condannato a più riprese per infrazione e contravvenzione alla LStup (RS 812.121) e per infrazione alla LStr (RS 142.20). Arrestato, è stato detenuto per 221 giorni nel Canton Ginevra, fino al 1° luglio 2015. Interrogato dalla Polizia cantonale ticinese il 2 luglio seguente, egli ha dichiarato di non volere rientrare in Mali e di non disporre dei necessari documenti per poterlo fare. Il medesimo giorno la Sezione della popolazione del Dipartimento ticinese delle istituzioni ha disposto la carcerazione in vista di rinvio coatto di A._ per la durata di sei mesi sulla base dell'art. 76 cpv. 1 lett. b LStr combinato con gli art. 75 cpv. 1 lett. g e 76 cpv. 1 lett. b n. 3 e n. 4 LStr. Ritenendo legale e adeguata la detenzione e dopo avere sentito l'interessato, il sostituto del Giudice delle misure coercitive l'ha confermata con decisione del 2 luglio 2015. B. Adito tempestivamente da A._ il Tribunale amministrativo del Cantone Ticino ne ha respinto il gravame con sentenza del 12 agosto 2015. Dopo avere a sua volta constatato la legalità e l'adeguatezza del provvedimento litigioso, la Corte cantonale ha evaso negativamente la richiesta dell'insorgente di essere rinviato in Spagna in virtù del regolamento di Dublino ("Regolamento (UE) n. 604/2013" del 26 giugno 2013 che stabilisce i criteri e i meccanismi di determinazione dello Stato membro competente per l'esame di una domanda di protezione internazionale presentata in uno degli Stati membri da un cittadino di un paese terzo o da un apolide [rifusione]; di seguito Regolamento UE 604/2013 del 26 giugno 2013), primo paese in cui avrebbe chiesto l'asilo. Dalle ricerche effettuate nel sistema Eurodac (database che permette ai paesi dell'Unione europea, tra l'altro, confrontando le impronte digitali, di sapere se un richiedente asilo o un cittadino straniero, che si trova illegalmente sul territorio di un paese dell'UE, ha già presentato una domanda in un altro paese dell'UE) risultava infatti che egli non aveva depositato una prima domanda d'asilo in Spagna, segnatamente alle Isole Canarie. La sua istanza volta ad essere scarcerato per esservi trasferito non poteva pertanto essere accolta. C. Il 10 settembre 2015 A._ ha presentato dinanzi al Tribunale federale un ricorso, con cui chiede l'annullamento della pronuncia querelata. Contesta la legalità della sua detenzione, adduce che le autorità cantonali non avrebbero effettuato le necessarie ricerche nel sistema Eurodac interpellando le autorità spagnole ed afferma che in virtù del regolamento di Dublino dev'essere trasferito in Spagna: rinviarlo pertanto in Mali disattenderebbe l'art. 9 Cost. Invitati a determinarsi, la Sezione della popolazione e il Sostituto del Giudice delle misure coercitive non si sono espressi, mentre il Tribunale cantonale amministrativo si è limitato a riconfermarsi nella motivazione e nelle conclusioni della sentenza impugnata. Da parte sua la Segreteria di Stato della migrazione SEM si è allineata al contenuto della citata sentenza. D. Con replica dell'8 ottobre 2015, il ricorrente ha ribadito i propri argomenti.