Sachverhalt: A. A._, ein im Jahr 1990 geborener Staatsangehöriger des Irak, reiste 2007 als Asylbewerber in die Schweiz ein. Das Bundesamt für Migration (heute: Staatssekretariat für Migration) trat mit rechtskräftig gewordener Verfügung vom 19. Dezember 2012 auf das Asylgesuch nicht ein und verfügte die Wegweisung. Am 20. August 2015 wurde A._ zu einer Freiheitsstrafe von fünf Jahren und neun Monaten verurteilt, namentlich wegen versuchter eventualvorsätzlicher Tötung und Raufhandels. Am 12. Januar 2016 wurde er per 1. Februar 2016 bedingt aus dem Strafvollzug entlassen. Am 1. Februar 2016 ordnete das Amt für Migration und Integration des Kantons Aargau gegen ihn Ausschaffungshaft an, welche das Verwaltungsgericht des Kantons Aargau mit Urteil vom 4. Februar 2016 bis zum 30. April 2016 bestätigte. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten, die mit dem Datum 1. Oktober 2015 versehen und am 14. März 2016 zur Post gegeben worden war, beantragte A._ dem Bundesgericht, das Urteil des Verwaltungsgerichts aufzuheben und ihn unverzüglich aus der Haft zu entlassen; eventuell sei die Sache zur neuen Begründung und zur Sachverhaltsabklärung an die Vorinstanz zurückzuweisen. Mit Urteil vom 18. März 2016 trat das Bundesgericht mangels hinreichender Begründung im vereinfachten Verfahren gemäss Art. 108 Abs. 1 lit. b AuG auf die Beschwerde nicht ein. Das SEM lehnte das am 1. Februar 2016 von A._ eingereichte Asylgesuch (Mehrfachgesuch) am 15. März 2016 ab, wies ihn abermals aus der Schweiz weg, ordnete an, er habe die Schweiz bis zum 1. April 2016 zu verlassen und beauftragte den Kanton Aargau mit dessen Vollzug. B. Das kantonale Migrationsamt verlängerte nach Anhörung von A._ am 18. April 2016 dessen Ausschaffungshaft um weitere drei Monate und ordnete eventualiter eine Durchsetzungshaft an. Mit Urteil vom 21. April 2016 bestätigte der Einzelrichter am Verwaltungsgericht des Kantons Aargau die am 18. April 2016 angeordnete Verlängerung der Ausschaffungshaft bis zum 30. Juli 2016, 12.00 Uhr, und wies damit implizit dessen Gesuch um unverzügliche Haftentlassung ab. C. Mit Beschwerde vom 27. Mai 2016 beantragt A._, das Urteil vom 21. April 2016 des Verwaltungsgerichts des Kantons Aargau sei aufzuheben und er sei unverzüglich aus der Haft zu entlassen; eventualiter sei das angefochtene Urteil aufzuheben und zu neuer Begründung und zur Sachverhaltsergänzung an die Vorinstanz zurückzuweisen. Er ersucht für das bundesgerichtliche Beschwerdeverfahren um unentgeltliche Rechtspflege und Verbeiständung. Die Vorinstanz, das kantonale Migrationsamt und das SEM schliessen auf Beschwerdeabweisung. Der Beschwerdeführer hat sich dazu am 13. Juni 2016 vernehmen lassen.