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.

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 an $n\times m$ matrix $A$ with singular values $\sigma_1,\ldots,\sigma_{r}$ and for $ 0 \leq p \leq 2 $: \begin{equation*} \sum \limits_{i=1}^{r} \vert \sigma_{i} \vert^p= C_p \int_{0}^{\infty} \log \left(1+\sum \limits_{k=1}^{r} S_{k}(A^*A) t^{k} \right)t^{-\frac p2 -1}dt, \end{equation*} where $S_k(A^*A)$ stand for the sum of the determinat of $k\times k$ principle submatrices of $A^*A$ and $C_p$ is a constant depenting on $p$.

When $A$ is Hermitian, singular values are equal to eigenvalues and 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$.