Sachverhalt: A. X._ (geb. 1979), ägyptischer Staatsangehöriger, heiratete am 15. Oktober 2010 eine Schweizer Bürgerin (geb. 1970); am 7. November 2010 wurde der gemeinsame Sohn Z._ geboren. Nur wenige Wochen danach trennten sich die Ehegatten, worauf das Amt für Polizeiwesen und Zivilrecht Graubünden am 18. April 2011 die Aufenthaltsbewilligung von X._ widerrief und ihn anhielt, das Land zu verlassen. Das Departement für Justiz, Sicherheit und Gesundheit Graubünden wies die hiergegen gerichtete Beschwerde am 3. August 2011 ab. Dieser Entscheid ist rechtskräftig (Nichteintretensentscheide des Verwaltungsgericht des Kantons Graubünden vom 31. Januar 2012 und des Bundesgerichts vom 5. Juni 2012 [Urteil 2C_538/2012]). B. Das Amt für Polizeiwesen und Zivilrecht Graubünden forderte X._ in der Folge erneut wiederholt auf, das Land zu verlassen. Nachdem X._ nicht mehr erreicht werden konnte, wurde er am 18. Juli 2012 zur Anhaltung ausgeschrieben und am 27. November 2012 in A._ verhaftet. Das Amt für Migration und Zivilrecht Graubünden ordnete noch gleichentags die Ausschaffungshaft an, welche das Zwangsmassnahmengericht des Kantons Graubünden am 29. November 2012 bis zum 26. Februar 2013 bestätigte. Dieser Entscheid wurde letztinstanzlich mit Urteil des Bundesgerichts vom 20. Februar 2013 bestätigt (Urteil 2C_57/2013). Am 21. Februar 2013 stimmte das Zwangsmassnahmengericht des Kantons Graubünden der Haftverlängerung bis zum 26. Juli 2013 zu; auch dieser Entscheid wurde rechtskräftig (Urteil des Bundesgerichts vom 28. März 2013 [2C_276/2013]). C. Am 25. Juli 2013 stimmte das Zwangsmassnahmengericht des Kantons Graubünden einer weiteren Verlängerung der Ausschaffungshaft bis zum 26. Dezember 2013 zu. Eine dagegen erhobene Beschwerde wies das Kantonsgericht Graubünden am 14. August 2013 ab. D. X._ erhebt Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, er sei in Aufhebung des angefochtenen Entscheids aus der Ausschaffungshaft zu entlassen, eventualiter sei die Sache zu neuem Entscheid an die Vorinstanz zurückzuweisen. Das Amt für Migration und Zivilrecht Graubünden beantragt Abweisung der Beschwerde. Das Kantonsgericht verzichtet auf Stellungnahme. Das Bundesamt für Migration äussert sich, ohne einen Antrag zu stellen. Der Beschwerdeführer äussert sich zu den eingegangenen Stellungnahmen.