We prove nontrivial bounds for general bilinear forms in hyper-Kloosterman sums when the sizes of both variables may be below the range controlled by Fourier-analytic methods (Polya-Vinogradov range). We then derive applications to the second moment of cusp forms twisted by characters modulo primes, and to the distribution in arithmetic progressions to large moduli of certain Eisenstein-Hecke coefficients on GL(3). Our main tools are new bounds for certain complete sums in three variables over finite fields, proved using methods from algebraic geometry, especially l-adic cohomology and the Riemann Hypothesis.