IO лучше в нескольких потоках не делать. Seek'и будут долгими.
Попробуйте реализовать сжатие многопоточно в памяти, а запись в файл сжатой информации уже последовательно, по одному файлу.
Посмотрите в сторону чего нибудь вроде TPL Dataflow. Он как раз для задач подобной вашей создавался.
