Assume you do a polyphase decomposition into $M$ shorter filters, because that's really the best you can do in exploiting the decimation properties of your system.
Your $M$ shorter filters are just that: FIR filters.
You can then go ahead and take these filters and decompose it into $c=\left\lfloor\frac KM\right\rfloor$ filters each.
That way, you get $cM$ parallelly computable filters, $K-M < cM \le K$, where $cM=K$ exactly when your $K$ is an integer multiple of $M$.
Note that I'd be rather surprised if you could get a huuuge performance boost out of this, assuming this is about computation on say a general-purpose CPU. The memory / cache bandwidth (and CPU cycles) occupied by deinterleaving or dealing with non-contiguous samples can kill performance rather quickly.
What I've seen is that people instead go and implement their $M$ shorter filters (which still might be massive!) as FFT-based fast convolution filters. Some FFT implementations (FFTw, specifically) allow you to multi-thread your FFT.
If you're not writing software for machines that prefer linear memory accesses, but, say, FPGA gateware, things look different. Often, significant gains come from exploiting symmetry of filter coefficients, or zero-taps in Nyquist-M filters; make sure your restructuring doesn't break these advantages!