Sachverhalt:
A. Die Firma E._ AG war als Arbeitgeberin der Ausgleichskasse des Kantons Zürich angeschlossen. Der Konkurs über die Gesellschaft wurde am ........ 2006 eröffnet und am ........ 2007 für geschlossen erklärt. Mit Verfügung vom 23. November 2007 verpflichtete die Ausgleichskasse S._ als Verwaltungsratspräsident der Gesellschaft zur Bezahlung von Schadenersatz für unbezahlt gebliebene Sozialversicherungsbeiträge (einschliesslich FAK-Beiträge, Verwaltungskosten, Verzugszinsen, Mahngebühren und Betreibungskosten) in der Höhe von Fr. 141'686.30. Die dagegen erhobene Einsprache vom 4. Dezember 2007 wies die Ausgleichskasse mit Einspracheentscheid vom 11. Juni 2008 ab.
B. Die dagegen erhobene Beschwerde wies das Sozialversicherungsgericht des Kantons Zürich mit Entscheid vom 12. April 2010 ab.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten lässt S._ beantragen, der vorinstanzliche Entscheid und der Einspracheentscheid vom 11. Juni 2008 seien aufzuheben, soweit sie die Nachbelastung von Sozialversicherungsbeiträgen (zuzüglich Zins und Kosten) für G._ im Gesamtbetrag von Fr. 114'274.90 beträfen. Zudem lässt er um unentgeltliche Rechtspflege ersuchen.
Die Ausgleichskasse und das Bundesamt für Sozialversicherungen (BSV) verzichten auf eine Vernehmlassung.

Erwägungen:
1. Die Zuständigkeit der II. sozialrechtlichen Abteilung des Bundesgerichts zum Entscheid über die streitige Schadenersatzpflicht erstreckt sich auch auf die Forderung für entgangene Sozialversicherungsbeiträge nach kantonalem Recht (Urteil 9C_704/2007 vom 17. März 2008 E. 1, nicht publ. in: <ref-ruling>, aber in: SVR 2008 FL Nr. 1 S. 1, 9C_720/2008 vom 7. Dezember 2009, E. 1).
2. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzung gemäss den Art. 95 f. BGG erhoben werden. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>), und kann deren Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>; vgl. auch <ref-law>). Mit Blick auf diese Kognitionsregelung ist aufgrund der Vorbringen in der Beschwerde ans Bundesgericht zu prüfen, ob der angefochtene Gerichtsentscheid in der Anwendung der massgeblichen materiell- und beweisrechtlichen Grundlagen (u.a.) Bundesrecht verletzt (<ref-law>), einschliesslich einer allfälligen rechtsfehlerhaften Tatsachenfeststellung (Art. 97 Abs. 1, <ref-law>). Das Bundesgericht darf nicht über die Begehren der Parteien hinausgehen (<ref-law>).
3. Die Vorinstanz hat die Bestimmungen über die Arbeitgeberhaftung (<ref-law>; <ref-law> in Verbindung mit <ref-law>) sowie die hiezu ergangene Rechtsprechung, insbesondere über Eintritt des Schadens und Zeitpunkt der Kenntnis des Schadens (<ref-ruling>, 128 V 10, 119 V 89 E. 3 S. 92), die subsidiäre Haftung der Organe eines Arbeitgebers (<ref-ruling>, 126 V 237, 123 V 12 E. 5b S. 15, je mit Hinweisen), den zu ersetzenden Schaden (<ref-ruling> E. 3a S. 444, 123 V 12 E. 5b S. 15, je mit Hinweisen), die erforderliche Widerrechtlichkeit (<ref-ruling> E. 2a S. 195 mit Hinweisen), die Voraussetzung des Verschuldens und den dabei zu berücksichtigenden - differenzierten - Sorgfaltsmassstab (<ref-ruling> E. 3a S. 202, ZAK 1992 S. 248 E. 4b, je mit Hinweisen; vgl. auch Thomas Nussbaumer, Die Haftung des Verwaltungsrates nach <ref-law>, in: AJP 9/96, S. 1081) zutreffend wiedergegeben. Darauf wird verwiesen.
4. In Frage steht die Schadenersatzpflicht des Beschwerdeführers für entgangene Sozialversicherungsbeiträge. Dabei ist nunmehr unbestritten, dass die Haftungsvoraussetzungen erfüllt sind und der Beschwerdeführer als Verwaltungsratspräsident der konkursiten Gesellschaft schadenersatzpflichtig ist. In Frage steht jedoch in masslicher Hinsicht, ob Bestandteil der Schadenersatzforderung auch Ausstände von Beiträgen sind, welche die Ausgleichskasse mit Nachzahlungsverfügung vom 26. März 2004 für die an G._ geleisteten Zahlungen festgesetzt hatte. Während die Vorinstanz erwogen hat, die Beiträge seien mit der Nachzahlungsverfügung rechtskräftig festgesetzt worden und deren Rechtmässigkeit im Schadenersatzverfahren nicht mehr zu überprüfen, da der Beschwerdeführer keine konkreten Beanstandungen vorgebracht habe, und deshalb bei der Schadenersatzforderung zu berücksichtigen, stellt sich der Beschwerdeführer auf den Standpunkt, die Beiträge in der Höhe von Fr. 114'274.90 hätten mit dem Temporärbüro G._ abgerechnet werden müssen, da es sich nicht um Lohn von G._, sondern um Entgelte für ausgemietete Arbeiter gehandelt habe, weshalb die ihm anzulastenden Beitragsausstände und damit die Schadenersatzforderung nur Fr. 27'411.40 betrage.
4.1 Nach der Rechtsprechung findet im Schadenersatzprozess gemäss <ref-law> eine Überprüfung der den Ausständen zu Grunde liegenden Beitragsforderungen nicht mehr statt, soweit sie auf einer Nachzahlungsverfügung beruht, die unangefochten in Rechtskraft erwachsen ist. Durch die Möglichkeit der Gesellschaft sowie des betroffenen Arbeitnehmers, gegen eine Nachzahlungsverfügung Beschwerde zu führen, ist genügend Gewähr dafür geboten, dass die Organe der zahlungsunfähig gewordenen Arbeitgeberin nicht mit ungerechtfertigten Schadenersatzforderungen belastet werden. Deswegen haben sich die Organe im Schadenersatzverfahren eine vor der Konkurseröffnung eröffnete Nachzahlungsverfügung (vgl. AHI 1993 S. 173 E. 3b) entgegenhalten zu lassen. Eine Ausnahme gilt dann, wenn die Nachzahlungsverfügung der juristischen Person in einem Zeitpunkt eröffnet wurde, in welchem die ins Recht Gefassten als Organ ausgeschieden waren (<ref-ruling> E. 5). Ebenfalls vorbehalten bleiben jene Fälle, in denen sich aus den Akten Anhaltspunkte für eine zweifellose Unrichtigkeit der durch die Nachzahlungsverfügung festgesetzten Beiträge ergeben (AHI 1993 S. 172 E. 3a; ZAK 1991 S. 125 E. II/1b, Urteil H 77/03 vom 18. Januar 2005 E. 7).
4.2 Entgegen der Auffassung der Vorinstanz hängt nach der dargelegten Rechtsprechung die Überprüfung der rechtskräftigen Beitragsverfügung im Schadenersatzverfahren nicht davon ab, ob sie beanstandet worden ist, sondern ob sich aus den Akten Anhaltspunkte für eine zweifellose Unrichtigkeit ergeben, was das Sozialversicherungsgericht von Amtes wegen festzustellen hat (<ref-law>). Zudem hat der (dannzumal noch nicht anwaltlich vertretene) Beschwerdeführer zwar nicht ausdrücklich in der vorinstanzlichen Beschwerde, wohl aber in der Einsprache vom 4. Dezember 2007 und in der folgenden Eingabe vom 16. Dezember 2007, auf welche er in der Beschwerde verwiesen hat, geltend gemacht, seine Zahlungen an G._ für die ausgemieteten Arbeiter hätten die Sozialversicherungsbeiträge umfasst.
4.3 Solche Anhaltspunkte für die zweifellose Unrichtigkeit der Beitragsverfügung ergeben sich hier aus den Akten: Die Arbeitgeberkontrolle vom 15. Februar 2004 ergab Abweichungen zwischen abgerechneter und beitragspflichtiger Lohnsumme für "G._" im Betrag zwischen Fr. 103'382 (2002) und 288'767 (2000). Da die Firma E._ AG den einzelnen Arbeitnehmern Löhne von maximal etwa Fr. 85'000.- bezahlte, ist es offensichtlich, dass die an G._ bezahlten Beträge nicht Lohn für diesen persönlich sein konnten, zumal dieser ab 1. Januar 1999 eine ganze Invalidenrente gestützt auf einen Invaliditätsgrad von 100% bezog. Vielmehr ist aus den Akten klar ersichtlich, dass die Zahlungen an G._ den Einsatz von Personal betrafen, welches dieser der Firma E._ AG ausgemietet hatte. Zwar geht nur aus der ersten Auftragsbestätigung vom 24. Juli 1995 ausdrücklich hervor, dass im vereinbarten Stundensatz, welchen die Firma E._ AG an G._ zu bezahlen hatte, auch die Sozialleistungen inbegriffen waren, doch enthalten auch die Abrechnungen für die folgenden Jahre eine Rechnung für einen bestimmten Betrag "pauschal" für ausgeführte Montagearbeiten. Das sind klare Hinweise dafür, dass es sich dabei um Ausleihpersonal handelt, welches von G._ angestellt war. Bei Temporärarbeitern gilt - anders als bei einer blossen Personalvermittlung (ZAK 1976 S. 147, H 117/74) - der Temporärbetrieb als Arbeitgeber, nicht der Einsatzbetrieb (Wegleitung des Bundesamtes für Sozialversicherungen über den Bezug der Beiträge, WBB, Rz. 1016; Urteil H 448/00 vom 14. September 2001, E. 2b; vgl. auch ZAK 1990 S. 129, H 28/89 E. 5). Bei unklaren Verhältnissen ist nach dem Grundsatz zu verfahren, dass vermutungsweise derjenige als abrechnungs- und beitragspflichtig gilt, der die Löhne ausbezahlt (ZAK 1990 S. 129, H 28/89 E. 5). Aktenkundig hat die Firma E._ AG die betreffenden Beträge nicht an die einzelnen eingesetzten Arbeitnehmer bezahlt, sondern an G._, so dass vermutungsweise dieser - und nicht die Firma E._ AG selbst - abrechnungs- und beitragspflichtig war.
4.4 Insgesamt ergeben sich somit aus den Akten klare Anhaltspunkte dafür, dass die Beitragsverfügungen vom 26. März 2004 zweifellos unrichtig waren. Demzufolge besteht im Schadenersatzverfahren keine Bindungswirkung der Nachzahlungsverfügungen. Daran ändert nichts, dass die Firma E._ AG die Nachzahlungsverfügungen nicht angefochten hatte. Entgegen der Auffassung der Vorinstanz kann nicht gesagt werden, die Firma E._ AG hätte zweifelsohne die Nachzahlungsverfügungen angefochten, wenn sie für die an G._ geleisteten Zahlungen gar nicht beitragspflichtig wäre. Die Nichtanfechtung der Beitragsverfügungen ist Voraussetzung, dass die genannte Rechtsprechung überhaupt zur Anwendung kommt, wonach Beitragsverfügungen nicht mehr überprüfbar sind, ausser wenn sich aus den Akten Anhaltspunkte für die zweifellose Unrichtigkeit ergeben; sie kann demzufolge nicht auch als Argument dafür dienen, dass die Verfügungen nicht zweifellos unrichtig waren.
Die Vorinstanz hätte frei prüfen müssen, ob der betreffende Betrag von der Firma E._ AG hätte bezahlt werden müssen. Indem sie dies unterlassen hat, hat sie den Sachverhalt unvollständig festgestellt, so dass das Bundesgericht nicht gebunden ist und die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen kann (<ref-law>), was die Aktenlage vorliegend erlaubt.
5. 5.1 Nach der dargelegten Rechts- und Sachlage war für die streitige Lohnsumme vermutungsweise nicht die Firma E._ AG, sondern G._ abrechnungs- und beitragspflichtig. Obwohl der Beschwerdeführer dies bereits im Einspracheverfahren dargelegt hat, hat die Beschwerdegegnerin nichts vorgebracht, was geeignet wäre, diese Vermutung umzustossen. Sie hat im Einspracheentscheid bloss ausgeführt, G._ sei nur bis 30. Juni 1998 als Selbstständigerwerbender der Ausgleichskasse des Kantons Aargau angeschlossen gewesen, so dass die von der Firma E._ AG in den Jahren 1999-2002 an G._ geleisteten Zahlungen nicht mit dieser abgerechnet worden seien. Massgebend ist aber nur, ob G._ die Beiträge hätte abrechnen und bezahlen müssen; ob er das effektiv getan hat, kann auf die Beitragspflicht der Firma E._ AG keinen Einfluss haben.
5.2 Fehl geht schliesslich der Hinweis der Beschwerdegegnerin im Einspracheentscheid, der Beschwerdeführer hätte bei G._ eine Bestätigung verlangen müssen, dass dieser hinsichtlich der Sozialleistungen korrekt abrechne: Es gibt keine Vorschrift, wonach derjenige, der - ohne selber abrechnungs- und beitragspflichtig zu sein - bei einer anderen Unternehmung Ausleihpersonal ausmietet, nachprüfen muss, dass der abrechnungs- und beitragspflichtige Arbeitgeber korrekt die Sozialversicherungsbeiträge abrechnet. Eine solche Nachprüfung wäre derart fern von jeglichem sozialüblichen Verhalten, dass ihre Unterlassung jedenfalls nicht als grobfahrlässige Missachtung von Vorschriften im Sinne von <ref-law> betrachtet werden könnte.
5.3 Damit beinhaltet die Schadenersatzforderung lediglich die - letztinstanzlich nicht mehr bestrittenen - Ausstände für die eigenen Arbeitnehmer der Firma E._ AG, nicht aber für die an G._ bezahlten Beträge. Das Quantitativ der entsprechenden Beträge ist unbestritten, nachdem der Beschwerdeführer beim von ihm annäherungsweise errechneten Betrag der auf G._ entfallenden Beitragsausstände auf eine exakte Ausscheidung der entsprechenden Mahn- und Betreibungskosten verzichtet und dieselben bei den Ausständen der Firma E._ AG berücksichtigt und sich die Beschwerdegegnerin dazu nicht geäussert hat.
6. Dem Ausgang des Verfahrens entsprechend hat die Beschwerdegegnerin die Gerichtskosten zu tragen (<ref-law>) und dem Beschwerdeführer eine Parteientschädigung zu bezahlen (<ref-law>). Dessen Gesuch um unentgeltliche Rechtspflege ist demzufolge gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen. Der Entscheid des Sozialversicherungsgerichts des Kantons Zürich vom 12. April 2010 und der Einspracheentscheid der Ausgleichskasse des Kantons Zürich vom 11. Juni 2008 werden dahingehend abgeändert, dass der von S._ der Ausgleichskasse des Kantons Zürich geschuldete Schadenersatz auf Fr. 27'411.40 festgelegt wird.
2. Die Gerichtskosten von Fr. 5'000.- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'800.- zu entschädigen.
4. Die Sache wird zur Neuverlegung der Parteientschädigung des vorangegangenen Verfahrens an das Sozialversicherungsgericht des Kantons Zürich zurückgewiesen.
5. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 3. August 2010
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Die Gerichtsschreiberin:
Borella Helfenstein Franke