Sachverhalt: A. A.a Im Jahre 1994 wurde die Kollektivgesellschaft X._ mit Sitz in T._ gegründet, bestehend aus den beiden Gesellschaftern H._ und R._. Am 12. Mai 2003 wurde die Gesellschaft infolge Austritts von H._ aufgelöst und im Mai 2003 im Handelsregister gelöscht. R._ führte das Geschäft unter der Einzelfirma S._ weiter. Am 8. Dezember 2005 wurde über diese Firma der Konkurs eröffnet und am 27. Januar 2006 mangels Aktiven eingestellt. A.b Mit Verfügung vom 15. August 2007 und Einspracheentscheid vom 12. März 2008 forderte die Ausgleichskasse des Kantons Bern (nachfolgend: Ausgleichskasse) von H._ Schadenersatz für nicht bezahlte Sozialversicherungsbeiträge der Jahre 1998 bis 2003 (einschliesslich Verzugszinsen und Kosten) in der Höhe von Fr. 85'919.85. B. Das Verwaltungsgericht des Kantons Bern wies die von H._ dagegen eingereichte Beschwerde mit Entscheid vom 12. Januar 2010 ab. C. H._ erhebt Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, der angefochtene Entscheid sei aufzuheben und es sei festzustellen, dass er nicht schadenersatzpflichtig sei. Die Ausgleichskasse schliesst auf Abweisung der Beschwerde. Das Bundesamt für Sozialversicherungen (BSV) hat keine Vernehmlassung eingereicht. Mit Verfügung des Instruktionsrichters vom 16. April 2010 wurde der Beschwerde aufschiebende Wirkung zuerkannt.