Fatti: A. A._ vive in Ticino dal 2000. Per motivi che non è necessario evocare, con scritto del 18 novembre 2015 la Sezione della popolazione del Dipartimento delle istituzioni del Cantone Ticino gli ha prospettato la revoca del permesso di domicilio e concesso dieci giorni per esprimersi in merito. Preso atto delle osservazioni ricevute, con decisione dell'11 gennaio 2016 la Sezione della popolazione gli ha poi revocato il permesso di domicilio, ordinandogli di lasciare la Svizzera entro il 10 marzo 2016. B. Per il tramite del suo legale, il 15 febbraio 2016 A._ si è rivolto al Consiglio di Stato chiedendo: che il ricorso fosse accolto (conclusione no. 1), di conseguenza: che la "decisione" del 18 novembre 2015 della Sezione della popolazione, acclusa in copia, fosse annullata (conclusione no. 2) e che l'ordine impartito di lasciare la Svizzera entro il 10 marzo 2016 fosse annullato (conclusione no. 3). Il Governo ticinese ha dichiarato il gravame irricevibile. Esso ha infatti considerato che l'atto impugnato, ovvero lo scritto del 18 novembre 2015 della Sezione della popolazione, non era una decisione, poiché non mutava affatto la situazione del ricorrente, e che quand'anche si fosse voluto concludere il contrario, il ricorso contro tale scritto sarebbe stato tardivo. Riguardo all'ordine di lasciare la Svizzera entro il 10 marzo 2016, la decisione del Consiglio di Stato non contiene per contro nessuno specifico rilievo. C. A._ si è allora rivolto al Tribunale amministrativo, lamentando che il Governo cantonale era incorso in un formalismo eccessivo. Ha infatti sostenuto che l'indicazione dello scritto del 18 novembre 2015 quale atto impugnato era da ricondurre ad una svista e che, già ad una semplice lettura del ricorso, che si riferiva pure al termine di partenza fissato per il 10 marzo 2016, il Consiglio di Stato avrebbe dovuto rendersi conto che oggetto del litigio era una revoca vera e propria ed interpellarlo. Con sentenza del 15 aprile 2016, il Tribunale cantonale amministrativo ha negato la violazione del divieto del formalismo eccessivo e respinto il gravame. Questo perché, siccome l'insorgente era patrocinato da un avvocato, il Consiglio di Stato poteva ritenere che quest'ultimo, agendo con la dovuta diligenza, si fosse accertato che l'atto contestato fosse effettivamente quello indicato nel gravame ed allegato al medesimo. Sempre secondo il Tribunale amministrativo, anche il fatto che nelle motivazioni si facesse rinvio alla revoca del permesso e all'esistenza di un termine di partenza non permette di concludere altrimenti. D. Con ricorso di diritto pubblico (recte: ricorso in materia di diritto pubblico) del 30 maggio 2016, A._ ha impugnato quest'ultima pronuncia davanti al Tribunale federale chiedendone l'annullamento e il rinvio degli atti all'autorità cantonale, affinché si esprima di nuovo sulla fattispecie. Il Tribunale amministrativo si è riconfermato nelle motivazioni della propria sentenza. Ad essa hanno fatto in sostanza rinvio anche la Sezione della popolazione e la Segreteria di Stato della migrazione. Il Governo ticinese si è invece rimesso al giudizio di questa Corte.