The number of ways to merge a permutation with itself
By @Max Alexeyev's solution above $N_{2k-1}^{\sigma}=tr(M_{k}(P_{\sigma}M_{k}P_{\sigma}^{-1}))$.
The eigenvalues and eigenvectors of $M_k$ are given here: Result attribution for eigenvalues of a matrix of Pascal-type. In particular $\mathbf{e}:=(1,\ldots,1)$ (the all-ones vector) is an eigenvector to the eigenvalue ${2k-1 \choose k}$ for $M_k$ (and then also for $P_\sigma M_k P_\sigma^{-1}$). Hence $\mathbf{e}$ is an eigenvector of $M_{k}(P_{\sigma}M_{k}P_{\sigma}^{-1})$ to the eigenvalue ${2k-1 \choose k}^2$. The desired inequality follows (since the product of symmetric positive definite matrices has only positive eigenvalues).
UPDATE: the inequality was already proved in the same way here (Lemma 4.3) https://doi.org/10.1016/j.ejc.2009.02.004
Here is a proof for when $\sigma$ is the identity permutation on $[k]$. Let $(\pi, s_1, s_2)$ be a valid triple for $k$. For each such triple, we can extend $\pi$ to a permutation $\pi'$ of $[2k+1]$ by placing $2k$ and $2k+1$ in positions $2k$ and $2k+1$ (in either order). So, there are two choices for $\pi'$. For each choice of $\pi'$, there are four ways to extend $(s_1,s_2)$ to $(s_1', s_2')$ since $s_1'$ can be either $s_1$ or $s_2$ extended by either $2k$ or $2k+1$ (and then $s_2'$ is fixed). Thus, each valid triple for $k$ can be extended to eight valid triples for $k+1$. Similarly, placing $2k$ and $2k+1$ in positions $2k-1$ and $2k+1$ (in either order), each valid triple for $k$ can be extended to two more valid triples for $k+1$. Thus, each valid triple for $k$ can be extended to ten valid triples for $k+1$. By induction, we get at least $10 \binom{2k-1}{k}^2$ such triples.
We now construct more valid triples for $k+1$.
Place $2k+1$ in position $2k+1$. Next choose a subset $X$ of $[2k]$ of size $k$ and a subset $I$ of $[2k]$ of size $k$ . Place the elements of $X$ in increasing order in the $k$ positions given by $I$. Place the elements of $[2k] \setminus X$ in increasing order in the positions given by $[2k] \setminus I$. This gives a permutation $\pi'$ of $[2k+1]$. Moreover, we can take $s_1'$ to be the elements of $X$ together with $2k+1$ and $s_2$ to be the elements of $[2k] \setminus X$ together with $2k+1$. This gives $\binom{2k}{k}^2$ more valid triples for $k+1$. Note that none of these triples is equal to the previously constructed triples since the common element of $s_1'$ and $s_2'$ in this case is $2k+1$, while the common element of $s_1'$ and $s_2'$ is at most $2k-1$ for the triples constructed by induction.
Finally, place $2k$ in position $2k$ and $2k+1$ in position $2k+1$. Choose a subset $X$ of $[2k-1]$ of size $k$ and a subset $I$ of $[2k-1]$ of size $k$. Place the elements of $X$ in increasing order in the $k$ positions given by $I$. Place the elements of $[2k-1] \setminus X$ in increasing order in the positions given by $[2k-1] \setminus I$. We can take $s_1'$ to be $X$ together with $2k$ and $s_2'$ to be $[2k-1] \setminus X$ together with $2k$ and $2k+1$. We can also interchange $s_1'$ and $s_2'$ (note that this is not symmetric). Thus, we obtain $2 \binom{2k-1}{k}^2$ more valid triples for $k+1$. Again, none of these triples is equal to a previously constructed triple since in this case the common element of $s_1'$ and $s_2'$ is $2k$.
Thus, there are more than $$12\binom{2k-1}{k}^{2}+ \binom{2k}{k}^2 =4 \binom{2k}{k}^2 > \left(\frac{2k+1}{k+1}\right)^2 \binom{2k}{k}^2=\binom{2k+1}{k+1}^2$$
triples for $k+1$.
For the general case, the first part of the above proof still works and gives a bound of at least $8^{k-1}$ triples for an arbitrary permutation $\sigma$ of length $k$.
Not sure how it's useful but here is an explicit formula for $N_{2k-1}^{\sigma}$.
For a given permutation $\sigma=(\sigma_1,\dots,\sigma_k)$, we have $$N_{2k-1}^{\sigma} = \sum_{i=1}^k \sum_{j=1}^k \binom{i+j-2}{i-1}\binom{2k-i-j}{k-i}\binom{\sigma_i+\sigma_j-2}{\sigma_i-1}\binom{2k-\sigma_i-\sigma_j}{k-\sigma_i}.$$ Here:
- $i$ and $j$ stand for the indices of the common element in $s_1$ and $s_2$, respectively;
- the product of first two binomial coefficients is the number of ways to interweave $s_1$ and $s_2$ into $\pi$ (the first coefficients accounts for what comes before the common element, the second coefficients accounts for what comes after);
- the product of last two binomial coefficients accounts for the content of $s_1$ and $s_2$ (the first coefficient accounts for the choice of elements smaller than the common one, the second accounts for the choice elements larger than the common one).
Btw, it is easy to see that for the fixed $i$ and $j$, $s_1$ and $s_2$ must share element equal $\sigma_i+\sigma_j-1$.
Since when $(i,j)$ runs over $[k]\times [k]$, the pair $(\sigma_i,\sigma_j)$ does the same, we can apply the rearrangement inequality to obtain an upper bound: \begin{split} N_{2k-1}^{\sigma} &\leq \sum_{i=1}^k \sum_{j=1}^k \binom{i+j-2}{i-1}^2\binom{2k-i-j}{k-i}^2\\ &= \binom{4(k-1)+1}{2(k-1)} \end{split} as proved in Combinatorial identity: $\sum_{i,j \ge 0} \binom{i+j}{i}^2 \binom{(a-i)+(b-j)}{a-i}^2=\frac{1}{2} \binom{(2a+1)+(2b+1)}{2a+1}$
ADDED 2020-10-31. I've checked the lower bound implied by the rearrangement inequality, and it turns out to be smaller than the required $\binom{2k-1}{k-1}^2$. Anyway, we can easily get another, also weaker, lower bound as follows.
From the explicit formula for $N_{2k-1}^\sigma$, it follows that $$N_{2k-1}^\sigma = \mathrm{tr}(M_kP_{\sigma}M_kP_{\sigma}^{-1}),$$ where $$M_k:=\left[ \binom{i+j-2}{i-1}\binom{2k-i-j}{k-i} \right]_{i,j=1}^k$$ and $P_{\sigma}$ is the permutation matrix corresponding to $\sigma$.
Since both matrices $M_k$ and $P_{\sigma}M_kP_{\sigma}^{-1}$ are symmetric, and share the set of eigenvalues $\left\{ \binom{2k-1}{i}\ :\ i=0..k-1\right\}$, we get this inequality: \begin{split} N_{2k-1}^\sigma &\geq \sum_{i=0}^{k-1} \binom{2k-1}{i}\binom{2k-1}{k-1-i} \\ & = \binom{4k-2}{k-1}. \end{split}