1. Encoding Actual URL
The path part, which we would call it key, of an encoded URL can consist of 6 ~ 8 digits in base62, up to desired uniqueness rate.
Randomly Generated
We can randomly generate those digits each within the range [0, 61].
Then we must check if the generated key is unique by consulting our key storage.
Aside: this checking process can be optimized with data structures like bloom-filter, provided we have to deal hundres of million records.
If we are unlucky, we may have a key collision; in this case, just re-generate another key until its unique.
To make encoding more efficient, we can have a standalone Key Generation Service(KGS) that generates those random key beforehand, and store them.