Given $k$ sorted lists, $O(n \log k)$ complexity, Mergesort rather than Heapsort
I would structure a formal proof of the runtime of your strategy as follows (This is, in structure, very similar to what you already wrote, but does not refer to omitted steps of an imaginary run of Mergesort.):

Arrange the $k$ lists as the leaves of an (almost) complete binary tree. Each internal node of the tree represents the merging of the two lists in its children. Clearly this tree has a height of $\lceil\log k\rceil$.

In this structure, the merges on each level of the tree combined will process each element exactly once.[1] Thus, they take a combined time in $\cal O(n)$. Adding up over all levels of the tree gives a runtime in $\cal O(n\log k)$.

Note that this argument does not require the lists to be of similar size.

Depending on the audience you may be required to elaborate some more on the $\cal O(n)$ bound. This can be done similar to the reasoning in the question:

Merging two lists with size $n_1$ and $n_2$ takes $n_1+n_2$ inserts and (in the worst case) $n_1+n_2-1$ comparisons. Thus, if we perform $i$ merges on a combined total of $n$ elements, they take $n$ inserts and (in the worst case) $n-i$ comparisons.



[1] If $k$ is not a power of $2$, the lowest level processes only a subset of the elements. Obviously the bound still holds for this case.