Oops, I mixed up the two phases. Marking is incremental (also in v8), and sweeping is parallelizable.

http://jayconrod.com/posts/55/a-tour-of-v8-garbage-collectio... gives a good overview of good GC techniques, championed in earlier lisps and functional languages.