Sachverhalt: A. Der 1941 geborene S._ bezog seit 1. Januar 1999 Arbeitslosenentschädigung. Mit Verfügung vom 25. Juni 2003 verneinte das Amt für Wirtschaft und Arbeit des Kantons Zürich (nachfolgend AWA) seinen Anspruch auf Arbeitslosenentschädigung ab 17. September 1999, woran es mit Einspracheentscheid vom 14. April 2004 festhielt. Hiegegen erhob S._ Beschwerde beim Sozialversicherungsgericht des Kantons Zürich. Mit Verfügung vom 17. Juli 2004 forderte die Arbeitslosenkasse GBI (nunmehr Unia Arbeitslosenkasse, nachfolgend Kasse) von ihm für den Zeitraum ab September 1999 bis November 2002 zu viel bezahlte Leistungen im Betrag von Fr. 126'467.45 zurück, wogegen er Einsprache erhob. Mit Verfügung vom 17. August 2004 sistierte die Kasse dieses Einspracheverfahren bis zur rechtskräftigen Erledigung des gerichtlichen Verfahrens betreffend den Einspracheentscheid vom 14. April 2004. Im Rahmen dieses Verfahrens entschied das Bundesgericht letztinstanzlich, S._ habe ab 1. Januar 2001 keinen Anspruch auf Arbeitslosenentschädigung (Urteil C 32/06 vom 29. März 2007). Mit Einspracheentscheid vom 14. Mai 2007 hob die Kasse die Verfahrenssistierung auf und wies die Einsprache des Versicherten gegen die Rückforderungsverfügung vom 17. Juli 2004 ab. B. In teilweiser Gutheissung der hiegegen erhobenen Beschwerde änderte das kantonale Gericht den Einspracheentscheid insoweit ab, als es den von S._ zurückzuerstattenden Betrag auf Fr. 63'397.65 reduzierte. Zur Prüfung der Erlassvoraussetzungen wies es die Sache an die Kasse zurück (Entscheid vom 30. Juni 2009). C. Mit Beschwerde beantragt S._, der kantonale Entscheid sowie die Rückforderungsverfügung seien aufzuheben und die Rückforderung wegen Verwirkung abzuweisen. Die Kasse und das Staatssekretariat für Wirtschaft (seco) verzichten auf eine Vernehmlassung. 