The minimum number of transposition in a product decomposition is $n-s$ where $s$ is the number of cycles in the permutation. Lets call it the transposition number.
The problem here is equivalent to finding the smallest number of transpositions to transform a permutation of the multiset to the canonical one, which we will define as $11...122...2...nn...n$.
Lets call a valid labeling a labeling of a permutation using labels $1_1, 1_2, ..., 1_m, 2_1, ..., 2_m,...n_1,...n_m$, so that a $k$ can only get a label $k_i, 1\leq i\leq n$
Our problem becomes equivalent to finding the minimum transposition number over all valid labelings of our permutation where the identity is labeled $\sigma_0 = 1_11_2...1_m2_12_2...2_m...n_1n_2...n_m$.
We first show that we can find a valid labeling with permutation number less than $m(n-1)$
We do it greedily: Let $\sigma = a_1a_2...a_{nm}$ be the multiset permutation. let $\sigma(a_i)$ be the first valid label not attributed (${a_i}_1$ if no label $a_i$ attributed, then ${a_i}_2$, etc.)
We compute the sequence $u_1 = a_1$, $u_n$ is the element of $\sigma$ at index $\sigma(u_{n-1})$ in $\sigma_0$ until we reach a cycle (that will happen when we meet a value for the second times.
For each element on the cycle only, we set the corresponding label. We iterate until all labels are attributed.
We repeat from an element with no label until every element has a label. At the end, we get a valid labeling. All the cycles find have length less than $n$, so there is more than $m$ cycle, hence transposition number is lower than $mn-m = m(n-1)$
Example: If $\sigma = a_1...a_6 = 323121$ We get the sequence $a_1, a_5, a_3, a_5...$ so we set the labels only for $a_3$ and $a_5$, so we get: $323_112_11$
We start again, from $a_1$ since it still does not have a label yet. We get the sequence $a_1, a_6, a_1, ...$. We set the labels for $a_1$ and $a_6$, so we get: $\sigma = a_1...a_6 = 3_223_112_11_1$
Continuing the process we then get $a_1...a_6 = 3_22_23_11_22_11_1$. We have $3$ cycles so the transposition number is $nm-3$ \leq m(n-1)$
We then exhibit a permutation that attains this bound
We easily verify that any valid labeling of $\sigma = 22...2...nn...n11...1$ induces less than $m$ cycles, so the transposition number will always be $mn-m$.
Example: $2_12_22_31_21_11_3$ induces 2 cycles, and $2_12_22_31_11_21_3$ indices 3 cycles (the maximum)