It would be interesting to know if you can spawn threads in SQL CLR. SQL Server already has its own multi-threading load distribution in place for query processing.

It sounds like you need to run asynchronous queries on the client. The client platform may or may not have this capability, but even if you break the task up into chunks, you still need to relieve the UI from waiting on this query execution. In .NET 2+, check out SQLCommand.BeginExecuteNonQuery.

That doesn't solve your problem, but it will make it more bearable to your users.