There are two ways to do this but one takes less steps inside the time critical loop so would take less time to compute each trial:

Public key addition (described above) steps

1) Generate new key pair
2) Add the generated public key to the provided public key
3) Hash and test
4) If not the vanity address match go to step 1)

Private key multiplication (described elsewhere) steps

0) Set the starting point of all key generation to the provided public key (instead of the normal point G)
1) Generate new key pair
2) Hash and test
3) If not the vanity address match go to step 1)

See how method 1) requires a larger modification to the vanity generation loop and adds a large computational step, point (public key) addition defined over the eliptical curve, into the time critical loop?

I believe that method 2) would run much faster.

After the vanity address is found the only difference between the two methods is that in method 1) the final private key is the modulo sum of the two private keys where as in method 2) is is the modulo product of the two private keys.