The GHC developers' point was that restricted side effects are necessary for automatic parallelization. Your answer seems to be, "I can parallelize languages with unrestricted side-effects... in sections where you restrict yourself to a side-effect-free subset."
Yes, I'm happy when a C++ compiler automatically optimizes my inner loop. But I'd rather be able to use "par" at the highest level of my program, and parallelize anything from XML parsing to physics simulation, without worrying that some library call ten functions down the stack will turn out to be non-reentrant.
"Traversing a linked list is inherently serial. [Theorists will point out that traversal can be done in parallel if you have a processor per node in the list. Feel free to buy that many Intel processors -- I own Intel stock.]"
One possible implementation would be to use a skip list where you have each core search each level.
Considering I spent years working on automatic parallelizing compilers for Fortran and C++, I'd say it is possible. I don't know why you consider the heavily computational kernels of C programs less interesting just because they don't have side effects or make IO calls.
For instance I worked on some algorithms to parallelize linked-list traversals, something that you would normally think is by definition serial.