Since you added a Solaris tag, which version are you using? As well as what filesystem(s) are you using? If UFS, can you move to ZFS which handles lots of smaller files better than UFS. It may have been Roche who benchmarked this.
ie: if you're on ZFS, you could create a dataset for each main dir and replicate it to a different filesystem or system where a higher level of compression is set. Including possibly dedup.
Based on the dir structure, it appears all the files live on the same FS that you're backing up to. So, a parallel option might not help any as I suspect IO will be the limiting factor, not CPU resources.
You could try throwing the jobs in the background as @Romeo Ninov suggests. Or even create a script for each directory and run them at the same time. In the end, only by playing and testing various options will you know for sure what may or may not help to find what best meets your needs. Including different archivers and compression algorithms.
For instance if speed is more important try a lower level of compression in
gzip or use
Also, if you don't think CPU is an issue, and have multiple, you could try using a pigz (parallel implementation of gzip) to see if that helps. That pkg is in the support repo for v11, but you'd have to obtain the source and compile it for earlier versions of Solaris.
Reco also a
timex in front of each command, as it might only be one of the dirs. giving you the slowness. If so, concentrate on optimizing that one.