If Progenitus "dies" to the command zone, can I shuffle my deck?
Yes, if you apply the replacement effects as described, you will still shuffle your library.

In the rules for the Shuffle keyword action, rule 701.19c says


  If an effect would cause a player to shuffle one or more specific objects into a library, that library is shuffled even if none of those objects are in the zone they’re expected to be in or an effect causes all of those objects to be moved to another zone or remain in their current zone.


In fact, one of the examples covers a very similar situation. It says


  Black Sun’s Zenith says, in part, “Shuffle Black Sun’s Zenith into its owner’s library.” Black Sun’s Zenith is in a graveyard, has gained flashback (due to Recoup, perhaps), and is cast from that graveyard. Black Sun’s Zenith will be exiled, and its owner’s library will be shuffled.


In that situation, like in this one, we have an instruction to shuffle the card into the library, and a replacement effect (created by Flashback) to move the card to another zone (exile) instead of the library.