An effective algorithm for convolution of very many long signals
So, I'm becoming a bit notorious with the whole "by using commonly available tools, how complex is your problem really?" business, but oh well:

I went ahead and simulated the "last" of your convolutions, i.e. I went ahead and picked up a FFT FIR (which is convolution by the overlap-save method Jason R mentioned) by dumping 500 Million random samples through a filter of 100,000 taps:



So, this flow graph produces an average total of 42 MS/s, or 420 (500x100,000) convolutions per second. The complete program, which includes initial FFT of the taps, calculating of the taps and the random pool, loading of libraries and set up of all, takes about 12 seconds. So, yes, doing this exact operation 5000 times would exceed the average coffee break's duration, and take nearly 17h. 

I tried timing the initial FFT of the tap vector (which the FFT filter blocks automatically), but I failed - it took much shorter than producing the taps vector itself. So I made a separate flow graph that just does 100,000-transforms of input data, and includes all the data generation/copying-overhead in my speed estimate. With that flow graph, my PC does 1900 FFTs per second, so it should take roughly half a millisecond to do a single one, or 2.5 s to do 5,000 of those.

Which also means that if you're smart, and just used the overlap-add algorithm as contained in the FFT FIR block and hoped that performance scales roughly linear with length of the input vector you're transforming, then every convolution would take about $\frac{12}5\text{ ms}= 2.4\text{ ms}$ longer than the previous, giving us a rough estimate of $\sum\limits_{n=0}^{5000} n\cdot 2.4\text{ ms}\approx 8\text{ h},\,25\text{ min}$.

Obviously, that leaves a bit of headroom for optimization. Now, Operlap-Add and Overlap-Save should actually scale exceptionally well to multi-core/distributed solutions. Also, doing a set of long FFTs also sounds like something that GPUs are great at.