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][1] 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][2] for a proof)


  [1]: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=5208528&url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5208528
  [2]: http://dl.acm.org/citation.cfm?id=1538904