I think that your database size is one of the main issues here. The TaskData is stored in the database as a serialized object. In one of our process the task data object in the db is 3kB large (and this is not a very large one). So millions of tasks result in a large database. You might want to have a look at the table T_TASK_DATA which contains the business data of your tasks.
Also when issuing task queries that search tasks by custom task data is not possible without loading each task from the database (of the respective type). So you should avoid such queries when you expect a large result.
I also experienced that the pub.task.taskclient:searchTasks service is very slow if you query several hundreds of tasks and you want to load the task data (query with includeTaskData=true).
#webMethods#webMethods-BPMS#MWS-CAF-Task-Engine