There is no reason why the inequality $s \leq C(m,n)\cdot |\{A_{ij}\neq 0\}|$ should hold.
Consider the adjacency matrix $A \in \mathbb{F}_2^{m \times n}$ of a left $d$-regular $(s, \varepsilon)$-expander. This matrix is sparse. Moreover, it can be shown that if $s$ is large enough, $A$ fulfills a Null-Space property (see Efficient and robust CS using optimized expander graphs for details).
Finally, $s$ need not be bounded. In theory, one can asymptotically choose $(n, s,\varepsilon)$ by penalizing the magnitude of $d$ and $m$ (see Unbalanced expanders and randomness extractor from Parvaresh-Vardy codes for a proof)
