Sachverhalt: A. M._ amtete seit der Gründung der X._ AG im Jahr 1993 bis Dezember 2007 als einziges Mitglied des Verwaltungsrats mit Einzelunterschrift. Vom 11. April 2006 bis 22. Februar 2008 war K._ als Geschäftsführer im Handelsregister eingetragen. Am xx. xx. 2008 wurde die Gesellschaft gestützt auf die Verfügung des Kantonsgerichts Schaffhausen vom xx. xx. 2008 wegen fehlenden Organen aufgelöst. Am 9. September 2008 wurde über das Vermögen der Gesellschaft der Konkurs eröffnet und am 5. Dezember 2008 mangels Aktiven wieder eingestellt. Mit Verfügung vom 12. Januar 2010 verpflichtete die Ausgleichskasse M._ zur Bezahlung von Schadenersatz für entgangene bundes- und kantonalrechtliche Sozialversicherungsbeiträge in der Höhe von Fr. 34'661.20 (einschliesslich FAK-Beiträge, Verwaltungskosten, Verzugszinsen, Mahngebühren und Betreibungskosten). Die hiegegen von M._ erhobene Einsprache wies die Ausgleichskasse mit Entscheid vom 25. Juni 2010 ab. B. Die gegen den Einspracheentscheid erhobene Beschwerde wies das Obergericht des Kantons Schaffhausen mit Entscheid vom 22. Juni 2012 ab, nachdem es vom Bundesamt für Sozialversicherungen (BSV) eine Stellungnahme vom 20. April 2011 zur Beitragspflicht der Arbeitnehmer der konkursiten Gesellschaft eingeholt hatte, in welcher auf die Bestätigung einer Sondervereinbarung der Deutschen Verbindungsstelle Krankenversicherung - Ausland (DVKA) vom 11. April 2011 verwiesen wurde. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten lässt M._ beantragen, der vorinstanzliche Entscheid sei aufzuheben und er sei von der Schadenersatzpflicht zu befreien. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Das kantonale Sozialversicherungsgericht und die Ausgleichskasse schliessen auf Abweisung der Beschwerde, während das BSV auf eine Vernehmlassung verzichtet. 