Your intuition is correct: in order to compute a wallet's balance bitcoind will scan through the entire blockchain, looking for a set of addresses that correspond to its own private keys. As you point out this is a rather time-consuming task. However we should note here that bitcoind needs to iterate through the blockchain and verify all transactions for validity anyway when bootstrapping, so checking if an address belongs to its wallet is rather trivial, compared to verifying scripts and signatures, so it's not adding much to that bootstrap time.
Once you are bootstrapped, you know that anything up to the point you verified is not going to change, so you can just incrementally scan new blocks as they come it, which often takes less than a second with todays code.
It is possible to build indices on which address was used in which transaction, which can help locating transactions that involve a certain transaction quickly, and there are wallets that make use of this (electrum, and all hardware wallets), however this is usefull mostly when you don't know all addresses at verification time, and you want to serve this information to users so they don't have to sync it themselves. To build the index however they themselves had to verify the entire chain. This is true for all blockchains by the way, either you are verifying the chain from its genesis, or you are trusting a third-party not to lie by omission (they can not report addresses that are yours), this is for example the case for metamask as well.
One final detail is that some seed schemas have a birthday date / height, which allows a wallet to start scanning from that height, since the seed basically says "don't bother scanning below, I had no addresses before this time". This saving is less efficient the older the seed is, since the skipped part will become smaller compared to the part that needs to be processed.
