We prove non-trivial upper bounds for general bilinear forms with trace functions of bountiful sheaves, where the supports of two variables can be arbitrary subsets in F-p of suitable sizes. This essentially recovers the Polya-Vinogradov range, and also applies to symmetric powers of Kloosterman sums and Frobenius traces of elliptic curves. In the case of hyper-Kloosterman sums, we can beat the Polya-Vinogradov barrier by combining additive combinatorics with a deep result of Kowalski, Michel and Sawin (2017) on sum-products of Kloosterman sheaves. Two Sato-Tate distributions of Kloosterman sums and Frobenius traces of elliptic curves in sparse families are also concluded.