Yes, it can be done, in at least two different ways, depending on how much you want to shorten them.
You can cut scarf joints (1:10 ratio) in the shaft, removing whatever length of paddle you want to remove. It's best to do this up toward the grip end, so the primary area of strain is not on the scarf joint. Do this such that the face of the scarf joints is aligned with the face of the paddle blade.
Another way is to just cut the grip off, use a tenon cutter to form a round tenon on the shaft end, and then put a t-grip on it. For the t-grip, you can use matching or contrasting wood, as you like.
Either way, you have to be careful that the grip will still be aligned with the blade when you're done, or it'll feel really weird in use.
I use epoxy, but Titebond 3 is supposed to be waterproof, too... I just haven't been willing to invest the time to build or repair a paddle, and use a glue that I'm not 100% certain will work.
Others may have more thoughts...