How a new wallet knows balances locked in P2SH transactions? If my old wallet created and submitted a P2SH TX to the blockchain, and I migrate to a completely different wallet, how can the new wallet detect that that UTXO belongs to me? Since the script is hashed, it can be anything and contain unpredictable information, like other PKHs in multisig transactions
In short, it knows because it knows. Whatever information was used to make the original wallet construct the addresses (whether that consists of a seed, a set of keys, a master key, a descriptor, a mnemonic phrase, ...) must be imported into the new wallet too.
The P2SH redeemscript is not created randomly: there is a procedure to generate it from keys the wallet has, and those keys may themselves also be generated from such information. What that information is depends on the standards or schemes involved, so it's hard to be very specific here.
Deterministic wallets have been standard since 2013 or so, and pretty much all wallets have some means of deterministically constructing keys from some fixed immutable piece of data. For single key policies (simple wallets) a wallet also needs information to turn those keys into scripts/addresses. Common ways include P2PKH (address contains a hash of the public key), P2WPKH (similar, but uses segwit for spending), or P2SH-P2WPKH (where the address is a P2SH address containing the hash of a segwit program that contains the hash of the public key). The wallet needs to know which (possibly more than one of these) is used to convert the keys into scripts, and that implies also a way for computing the redeemscripts involved. Sometimes this choice is implicit in the standard being followed; sometimes it needs to be imported/chosen specifically.
For multisignature or other policies it is more complicated, as wallets also need to know how the other participants generate their keys, but this information is always needed - both in the first and the second wallet.