In the special case $a_{ij} = \pm 1$, $2(n-1)$ is a lower bound, for every $n>0$.
As a comment by T. Tao above, the problem resembles the sharp Littlewood conjecture on the minimum of the $L^{1}$-norm of polynomials (on the unit circle in the complex plane) whose absolute values of coefficients are equal to $1$. In the special class of polynomials with $\pm 1$ coefficients, Klemes proved the sharp Littlewood conjecture (see here).
The proof of Klemes gives us the following equality, for a Hermitian matrix $A$ with eigenvalues $\lambda_1,\ldots,\lambda_{n}$: \begin{equation*} \sum \limits_{i=1}^{n} \vert \lambda_{i} \vert= C \int_{0}^{\infty} \log \left(\sum \limits_{k=0}^{n} S_{k}(A^{2}) t^{k} \right)t^{-\frac{3}{2}}dt, \end{equation*} where $S_k(A^2)$ is sum of the determinat of $k\times k$ submatrices of $A^2$ and $C$ is a constant.
By obtaining a "good" lower bound for $S_{k}(A^2)$, when $A$ is a matrix of the form described in the question, we can establish the lower bound in the special case $a_{ij} = \pm 1$.
Actually, this approach proves a conjecture by W. Haemers on Seidel energy of graphs.