Polynomial bound on sum of strings
You can also prove this using automata theory. For a set $S = \{s_1,\ldots,s_k\}$ of strings over $\Sigma$, consider the following language over $\Sigma \cup \{1,\ldots,k\}$:
$$ L_S = (1s_1+2s_2+\cdots+ks_k)^+. $$
This language is accepted by a DFA of size roughly $\|S\| := |s_1|+\cdots+|s_k|$. The exact size depends on the model of DFA - in our case it makes sense to ask for at most one transition out of each state with a given label (rather than exactly one transition, as is usually the case).

Now we want to do the same, but for two sets of strings $A = \{a_1,\ldots,a_m\}$, $B = \{b_1,\ldots,b_n\}$. To this end, we consider languages $L_A,L_B$ which are defined as before, but with two differences:


$1,\ldots,k$ are replaced with $A_1,\ldots,A_m$ for $L_A$ and $B_1,\ldots,B_n$ for $L_B$.
The symbols $A_1,\ldots,A_m$ are ignored in $L_B$, and the symbols $B_1,\ldots,B_n$ are ignored in $L_A$.


As an example, suppose that $A = \{a,ba\}$ and that $B = \{ab,a\}$. Then the following word will be in our language: $A_1B_1aA_2bB_2a$.

As before, we can construct DFAs for $L_A,L_B$ having roughly $\|A\|,\|B|$ states, respectively. Using the product construction, we get a DFA of size roughly $\|A\|\cdot\|B\|$ for the intersection. It is well-known (and can be proved using the pigeonhole principle) that if a DFA having $N$ states accepts any word, then it accepts some word of size less than $N$. This implies your claim.



In terms of lower bounds, it is easy to refute your conjecture that $2nL$ is enough. Consider $A = \{ 0^L \}$ and $B = \{ 0^{L-1} \}$. It is not hard to check that the minimal solution has length $L(L-1) \approx L^2$.

It's less clear what is the correct dependence on $n$.