Сначала я бы попытался преобразовать файл Excel в файл CSV, как упомянул ваш собеседник. Вытащить объект CSV гораздо дешевле, чем объект Excel. Вы можете сделать это, просто используя Microsoft.Office.Interop.Excel и вызвав:
myExcelWorkbook.SaveAs(@"c:\myExcelWorkbookIsNowA_CSVFile.csv",......)
Затем поработайте с CSV-файлом для манипулирования данными. И посмотрите, улучшится ли производительность.