This solution was originally inspired by athin's solution, but with an improved way of generating the sum of the two smallest numbers. Now, it is a variant on Bass's solution since, as suggested by them in the comments, we can change the sum to a max, and then we don't need to subtract the smallest number at the end.
Let's index the inputs as $x_0, x_1, \dots, x_{m-1}$. Write the numbers $0, 1, \dots, m-1$ in binary. For each $k=1,2,\dots,\lceil\log_2 m\rceil$, let $A_k$ be the min of all $x_i$ such that $i$ has a $0$ in the $k$-th position; let $B_k$ be the min of all $x_i$ such that $i$ has a $1$ in the $k$-th position. Then our solution is $$\min(\max(A_1,B_1),\max(A_2,B_2),\dots,\max(A_k,B_k)).$$ The number of $x$'s in this expression is $m \lceil \log_2 m \rceil$.
Here's why this works:
Each $\max(A_k,B_k)$ will be the max of two elements, so it's at least the second-smallest element. On the other hand, if $x_i$ and $x_j$ are the two smallest $x$'s, then there has to be some position $k$ where the binary representations of $i$ and $j$ differ; say, $i$ has a $0$ in the $k$-th position, and $j$ has a $1$. Then we'll get $A_k = x_i$ and $B_k = x_j$, so $\max(A_k,B_k) = \max(x_i,x_j)$ will definitely show up in the min we take. No other $\max(A_{k'}, B_{k'})$ can be smaller, so $\max(x_i,x_j)$, the second-smallest element, is our final answer.
Here's an example of the finished formula for $m=8$:
$$\min\Big(\max(\min(x_0,x_2,x_4,x_6),\min(x_1,x_3,x_5,x_7)), \max(\min(x_0,x_1,x_4,x_5),\min(x_2,x_3,x_6,x_7)), \max(\min(x_0,x_1,x_2,x_3),\min(x_4,x_5,x_6,x_7))\Big).$$
And here is a diagram of that solution drawn by humn:
We can sort of generalize this to an $O(m \log m)$ solution for finding the $k^{\text{th}}$ smallest element, by relying on a Math.SE answer written a year ago by a clever and handsome individual.
I say "sort of" because this is only a random construction. Not in the sense that it works only on some random inputs. It's random in the sense that I'll describe a method for generating a formula with some randomness in the method; with positive probability, it'll give us a formula that always works for all inputs.
Here's how.
A "clause" in our formula looks like the following. We split $\{1,2,\dots,m\}$ into $k$ sets $S_1, S_2, \dots, S_k$, and then take $$\max\{\min\{x_i : i \in S_1\}, \min\{x_i : i \in S_2\}, \dots, \min\{x_i : i \in S_k\}\}.$$ The value this generates is always a max of $k$ distinct elements, so it's at least the $k^{\text{th}}$ smallest. And if the $k$ smallest elements happen to be distributed evenly between $S_1, \dots, S_k$, then the value of the clause is the $k^{\text{th}}$ smallest element.
To make sure this always happens, we generate many clauses at random: for each $i \in \{1,2,\dots,m\}$, we choose (independently and uniformly at random) to put it in one of $S_1, \dots, S_k$. As shown in the Math.SE answer I linked to, if we generate $\frac{k^k}{k!} \ln \binom mk \approx k e^k \ln m$ clauses, then with positive probability it will be true that for any $k$ variables, there's a clause that separates them. When this happens, our final formula will be the min of all these clauses.
