Preface: I'm not an engineer; just a working carpenter, so any of this should be validated by plan approval by your 'authority having jurisdiction' (AHJ). They may ask for engineering stamps.
Another note, there are many perfectly correct ways to build things. I'm only going to talk about what makes the most sense to me personally. That shouldn't imply that other solutions are worse -- some might actually be better.
This is a sub-answer, related specifically to splitting the posts of your pergola into 2 sections -- the length below the deck, and everything from the surface of the deck up. There's a few reasons to do this... if you're going to put a post below grade, it should be pressure treated (PT). Personally, I wouldn't be happy about my pergola posts above the deck being PT. Even if the PT wasn't an issue, actually standing 16' or 22'-6x6 posts would be difficult without a bunch of manpower or a crane. (Or a tractor, as noted above.)
So, let's build a support for the pergola that just happens to live below the deck. You can sink your posts in deep holes or simply make deep holes full of concrete with a bracket on top of the concrete. If this was my job, I'd use brackets on top of a tube of concrete (less lumber to buy and carry, better resistance to rot; though a bit more concrete to pour and if you choose a bracket that is actually set in the wet concrete, you need to take care to get it perfectly placed). Posts will go up to your existing deck and connect with sturdy through bolts. You'll also want to add extra joists and rim boards to thoroughly box in the top of the 4 post structure we're building. At grade, you'll also want to box the posts to prevent any movement. Further (as noted by @MichaelKaras), you'll want cross-bracing to prevent racking or twisting. Here's a terrible pic:
Those under-deck posts will be where you want the pergola posts to connect and carry straight down. A direct connection is far better than pushing the under-deck post to the underside of the existing deck. (Don't know what your deckboards are, but if they're wood, they aren't well suited to being sandwiched between low and high posts for a variety of reasons.) Various brackets and alternate solutions exist to connect posts... if you try to make it so that they will never move (up or sideways), then you're on the right track. They also should be almost as strong as if the two posts were one piece of wood.
But since they aren't ever going to be as strong as one piece of wood, you need to engineer some bracing at the top of the pergola that'll keep the structure from twisting and racking. I would lean toward a pair of 2x8 or 2x10s on each side, with a knee brace (8 in all) in each direction. Here's one I made earlier:
(This was a while ago, but I think it was about 13' square, 11' high, 2' knee braces, 2x10 lumber at the top. Lag screws to connect the knee braces to the posts; through bolts to connect the 2x lumber. If you really shoved it, it had a tiny bit of flex, but it was pretty solid. If you stare hard, you'll see that the knee braces are let into the post by a tiny bit for a better connection.)
If you need any points clarified, just ask.