$m = \Omega(k \log(n/k))$ is a lower bound for any compressive sensing scheme, not just $\ell_1$-minimization using RIP guarantees on the measurement matrix. In fact, the recovery algorithm need not be polynomial time, and the measurement matrix may be adaptive (in the sense that the $i$'th row of the matrix can depend on the inner product of the input vector with rows $1$ through $i-1$).
Let me sketch the argument for non-adaptive measurements. If $K$ is a subset of $\ell_p^n$, then the Gelfand $m$-width of $K$ is defined to be:
$$d^m(K) = \inf_{A: \mathbb{R}^{m \times n}} \sup_{x \in K \cap \ker(A)} \|x\|_p$$
Define the compressive $m$-width as:
$$E^m(K) = \inf_{A: \mathbb{R}^{m \times n}, \Delta: \mathbb{R}^m \to \mathbb{R}^n} \sup_{x \in K}\|x - \Delta(A x)\|_p $$
Note that $\Delta$, the reconstruction procedure, can be arbitrary.
Lemma 1: If $K$ is symmetric ($K = -K$), then $E^m(K) \geq d^m(K)$.
Proof: Take some arbitrary matrix $A \in \mathbb{R}^{m \times n}$ and function $\Delta: \mathbb{R}^m \to \mathbb{R}^n$. By definition, $d^m(K) \leq \sup_{x \in K \cap \ker(A)} \|x\|$. On the other hand, for any $x \in K \cap \ker(A)$:
$$\|x\| \leq \frac12 \|x-\Delta(0)\| + \frac12 \|-x-\Delta(0)\| \leq \sup_{x \in K} \|x-\Delta(Ax)\|$$
So, we have $d^m(K) \leq \sup_{x \in K \cap \ker(A)} \|x\| \leq E^m(K)$. $\blacksquare$
Now, for the connection with compressive sensing, suppose we have an integer $k \geq 1$, matrix $A \in \mathbb{R}^{m \times n}$ and a function $\Delta: \mathbb{R}^m \to \mathbb{R}^n$ such that for all $x \in \mathbb{R}^n$:
$$\|x - \Delta(Ax)\|_p \leq \frac{C}{k^{1-1/p}} \min_{k\text{-sparse } z} \|x - z\|_1$$
where $C$ is a constant. Let $B_1$ be the unit $\ell_1$-ball, viewed as a subset of $\ell_p^n$, for $1< p\leq 2$. We clearly have that:
$$E^m(B_1) \leq \frac{C}{k^{1-1/p}} \sup_{x: \|x\|_1 \leq 1} \min_{k\text{-sparse } z} \|x - z\|_1 \leq \frac{C}{k^{1-1/p}}$$
But we also have a lower bound for the Gelfand width of $\ell_1$-balls.
Theorem 2: There exists a constant $c_1$ such that: $$d^m(B_1) \geq c_1 \min\left(1, \frac{\log(n/m)}{m}\right)^{1-1/p}$$
Combining with the above, we have that:
$$c' \min\left(1, \frac{\log(n/m)}{m}\right) \leq \frac1k$$
Thus, if $k$ is large enough, this gives the lower bound, $m = \Omega(k \log(n/k))$.
The proof can be extended without much difficulty to the adaptive setting. The assumption that $k$ is sufficiently large can also be removed.
I learnt of this argument from Chapter 10 of Foucart and Rauhut's recent book, "A Mathematical Introduction to Compressive Sensing". It's due to Cohen, Dahmen and Davenport ("Compressed sensing and best k-term approximation", 2009). Theorem 2 is due to Garnaev and Gluskin ("On widths of the Euclidean ball", 1984). Foucart, Pajor, Rauhut and Ullrich ("The Gelfand widths of $\ell_p$-balls for $0<p\leq 1$", 2010) give a relatively simple proof of it. In fact, this latter proof is based on a lower bound for the number of measurements needed for exact-recovery of $k$-sparse vectors.
