For starters consider the following candidate factorization: $ (x^2+ax-1)(x^2+bx-1)=x^4+(a+b)x^3+(ab-2)x^2-(a+b)x+1. $ This works if $a+b\equiv 12$ and $ab\equiv 16$. The discriminant of the quadratic $ (T-a)(T-b)=T^2-(a+b)T+ab=T^2-12T+16 $ is equal to $20$. So if $20$ is a quadratic residue modulo $p$, then we have a factorization of this kind. As $20=2^2\cdot5$ we are really interested in, whether $5$ is a quadratic residue modulo $p$ or not. By quadratic reciprocity this happens, iff $p$ is a quadratic residue modulo $5$. So we get that a factorization of this kind exists, iff $p\equiv\pm1\pmod5.$ Of course, this is equivalent to $p$ being congruent to either $1,9,11$ or $19$ modulo $20$.
I don't know, if it is easy or difficult to extend this elementary argument and detect, whether these quadratic factors will split further. Also, this argument obviously doesn't rule out the possibility of other quadratic factors, but you seemed to have the cases $p\equiv\pm2\pmod 5$ covered already.