If the number of leaves is exactly a power of two (i.e., n = 2k), then the number of hashes performed is exactly n-1. This is easy to see: every hash operation takes two inputs, and reduces them to a single one. After n-1 operations, that means n nodes are reduced to 1, and that one is the Merkle root.
When the number of leaves is not a power of two, it's a bit more complicated. Whenever a "level" of the Merkle tree has an odd number of leaves, a hash operation is still performed for the last one, but it only takes one input. So every time this happens, it means an addition hash operation on top of the n-1 that are expected otherwise.
How often does that happen? Let's look at the level sizes for n=9..16 leaves:
- 9 → 5 → 3 → 2 → 1: 11 hashes (n - 1 + 3 odd levels)
- 10 → 5 → 3 → 2 → 1: 11 hashes (n - 1 + 2 odd levels)
- 11 → 6 → 3 → 2 → 1: 12 hashes (n - 1 + 2 odd levels)
- 12 → 6 → 3 → 2 → 1: 12 hashes (n - 1 + 1 odd level)
- 13 → 7 → 4 → 2 → 1: 14 hashes (n - 1 + 2 odd levels)
- 14 → 7 → 4 → 2 → 1: 14 hashes (n - 1 + 1 odd level)
- 15 → 8 → 4 → 2 → 1: 15 hashes (n - 1 + 1 odd level)
- 16 → 8 → 4 → 2 → 1: 15 hashes (n - 1 + 0 odd levels)
The number of odd levels is exactly equal to the number of 1 bits set in the binary representation of the difference between the number of leaves and the next power of two. For example, for n=11 leaves, the next power of two is 16, the difference between those is 5, which is written in binary as 1012, which has two 1s. Thus, the number of hashing operations is 11-1 + 2 = 12 hashes.
Without knowing anything about the structure of the number of leaves, a lower bound on the number of hashing operations is n-1, and an upper bound is n-1+log2(n-1).
