Why must basis sets used in computations be non-orthogonal?
It does not have to be non-orthogonal. The basis set can be arbitrary, and one usually uses the chemically motivated Ansatz with atomic orbitals (LCAO), which just happen to be non-orthogonal. An alternative would be to use a plane wave basis set, which are orthogonal.