Scalaz is using foldLeft as well https://github.com/scalaz/scalaz/blob/c3133dff94ae21025014f33c1d2736bdf98e96f3/core/src/main/scala/scalaz/std/Vector.scala#L34

I do not understand where the difference comes from :(

The +++ for Validation needs a Semigroup. Maybe the Semigroup implementation of List and Vector is not optimal?
(like concatenating 2 lists or 2 vectors together, instead of simply adding an element)

Possible https://github.com/scalaz/scalaz/blob/c3133dff94ae21025014f33c1d2736bdf98e96f3/core/src/main/scala/scalaz/std/Vector.scala#L97

I guess replacing the whole Monoid append operations on immutable datastructure with a mutable collection builder with a fast append operation did the trick.