Run the commands in background

rm -rf dir &; rm -rf dir2 &;

syntax

long_command with arguments > redirection &

you can capture any messages by redirecting the command output to a file.

This links will help ==> http://tldp.org/HOWTO/Bash-Prog-Intro-HOWTO-3.html

Edit :

The question title & given example gives an impression like the issue is very small. But an added bounty showing the seriousness of the issue.

It would be better if you specify the nature of your files. However, I am providing some split based deletion which can implemented as parallel executions You can try below options based on your requirement.

deleting files by size

find /yourpath/folder1 -size +1048576 -exec rm -f {} \; &
find /yourpath/folder2 -size +1048576 -exec rm -f {} \; &

deleting files by extension

find extensions by using below command

ls -l /yourpath/folder1 | awk '{print $9}' | awk -F. '{print $(NF)}' |sort |uniq

you may get result like

.txt
.log
.tmp
.zip

now, delete the files based on extensions

find yourpath/folder1 -name '*.txt' -exec rm {} \; &
find yourpath/folder1 -name '*.tmp' -exec rm {} \; &
find yourpath/folder1 -name '*.log' -exec rm {} \; &
find yourpath/folder2 -name '*.txt' -exec rm {} \; &
find yourpath/folder2 -name '*.tmp' -exec rm {} \; &
find yourpath/folder2 -name '*.log' -exec rm {} \; &

deleting files by modified time

below command tries to delete files older than 5 days.

find yourpath/folder1 -mtime +5 -exec rm {} \;

OR

find yourpath/folder2 -mtime +5 |xargs rm 

deleting folder & it's sub folders including it's files

find foldername -exec rm -rf {} \; &

Just in case you want to do more than removing directories in parallel, you can do a lot of parallel fancy stuff with GNU parallel. As it often is not a base utility in distributions, you may need to install it using your favourite package manager, e.g. apt-get install parallel.

But then, you can do cool stuff like this, say you run 4 parallel processes, want to show the progress, no nag notice and let in parallel run a sleep command waiting for 5s, 10s, 15s, 20s each.

$ parallel -j 4 --progress --no-notice sleep ::: 5 10 15 20 

Computers / CPU cores / Max jobs to run
1:local / 4 / 4

Computer:jobs running/jobs completed/%of started jobs/Average seconds to complete
local:0/4/100%/5.0s  

Your example would be running like this:

$ parallel --no-notice rm -rf ::: dir1 dir2 dir3 

Feel free to consult the fine tutorial.

I had to clean up some folders in /media as fast as possible.
The following command was able to delete 9T of data on each of the 80 disks in roughly 5mn

$ sudo find /media -maxdepth 2 -name "data-8" -type d | while read folder; do eval "sudo rm -rf ${folder} &"; done

This kicked 80 parallel rm -rf in the background