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 {} \; &

&
?rm -rf dir1/& rm -rf dir2/
. Thus bash will not wait for the first command (deleting dir1) to start the second one. – Auzias Feb 20 '16 at 14:51