Analysis and algorithmic complexity of the Constant Q transform
I didn't verify each exact step of your analysis, but it seems that you're overestimating the memory part by a huge margin. A lot of the kernels are identical except for the exact tiem moemnt at which they're applied. In fact, you only have one kernel per level. So for a typical music application you have only 12 levels per octave, and thus 12 kernels. Over a 10 octave range (20 Hz-20 kHz) that's still only 240 levels. The paper you reference uses quarter-tone resolution (24/octave) and 5 octaves. That's just a design choice.

Next, you state that "With their implementation, they store the kernels in full size". I doubt it. The paper explicitly mentions the effect of trimming the kernels (see Figure 3) and states that the kernels are trimmed to 6 values max (and sometimes just 1 !). This saves both memory and time. The exact amount does depend on the trimming applied.