If Coinomi creates a new Public address for each "receive", does that also imply another private key for each public address?
Yes.
Yes, I've got the recovery phrase backed up.
Good!
But let's say I received Litecoin at ten different addresses in my Coinomi wallet.
How does the key generator know that there were 10 addresses?
It will generate the 1st address, and then check if it has been used on the blockchain. It doesn't matter if it contains nothing right now, what's important is whether there was activity at some time or not. Then it moves on to the 2nd address and checks that one. This process continues until it has checked 20 addresses in a row without activity. The count of 20 is called the "gap limit". In some wallets, it is configurable.
Why would there be a gap? Lets say you gave out unique payment addresses to 10 coworkers to pay their share of the lunch tab. Then you gave out addresses to your online customers - and they paid. Now lets say all 10 coworkers stiffed you. You'd have a gap of ten unused addresses.