If I understand you correctly,
you're asking a question equivalent to
"Given the number of leaf nodes, what's the total number of nodes in a binary tree?"
One special case -- the "perfect binary tree" -- occurs when you get a number of leaf nodes that is exactly some power of two -- n_leaves = 2^x.
In that case,
the total number of nodes is n_nodes = 2*n_leaves - 1.
I'm pretty sure that formula is true for any strictly binary tree -- i.e., a tree where every non-leaf node has exactly two children -- even ones that are terribly unbalanced.
That's because every strictly binary graph can be created by starting with a single (leaf) node, and repeatedly adding a pair of nodes.
At each step, a leaf in the graph is converted to a non-leaf node, and two leaves are added -- a net increase of one leaf node and one non-leaf node.
Since we started with only a single root leaf node,
the number of leaf nodes n_leaves is always exactly one more than the number of non-leaf nodes n_non_leaves.
So the total number of nodes n_nodes = n_leaves + n_non_leaves in a strictly binary graph is always n_nodes = 2*n_leaves - 1.
Is your Merkle tree always a "strictly binary tree"?
For some reason I thought that, if there were an odd number of leaves in the tree, that the left-over hash (after all the other hashes were paired off) was passed up to the next level unchanged.
You seem to be saying that the left-over hash is re-hashed to generate its part of the next level.
It escapes me what is the point of re-hashing an internal hash with only one child, but I'm sure you have your reasons.
I'm assuming that the root node always has 2 or 0 children, never 1 child.
In the special case where the number of leaves has one fewer than some power of two -- n_leaves = 2^x - 1 -- then the internal graph of non-leaves looks exactly like the "perfect binary tree" that had 2^x leaves, so there are 2^x - 1 non-leaf nodes,
so the total number of nodes is n_nodes = 2*n_leaves.
In the other extreme special case where the number of leaves is one greater than some power of two -- n_leaves = 2^x + 1 -- then the internal graph of non-leaves has one section that looks exactly like the "perfect binary tree" of 2^x leaves, plus a linear rail along the side that goes all the way up to the root.
There are 2^x-1 non-leaf nodes in the "perfect binary tree" section.
There are x+2 non-leaf nodes in the "linear rail" section (including the root node).
So the total non-leaves is 2^x-1 + x+2 = 2^x+1+x = n_leaves + log2( n_leaves-1 ) = non_leaves.
So the total number of nodes = leaves+non_leaves = 2*n_leaves + log2( n_leaves-1 ).
I'm pretty sure any other number of leaves will give something intermediate between these special cases -- a linear rail that runs only partially up the right side.
It escapes me at the moment exactly how to calculate how many nodes will be in that linear rail. Perhaps just knowing the minimum and maximum range will be adequate for your application:
In all cases, 2*n_leaves - 1 <= n_nodes <= 2*n_leaves + log2( n_leaves-1 ).