We study the maximum k-coverage problem in the general edge-arrival streaming model: given a collection of m sets F, each subset of a ground set of elements U of size n, the task is to find k sets whose coverage is maximized. The sets are specified as a sequence of (element, set) pairs in an arbitrary order. Our main result is a tight (up to polylogarithmic factors) trade-off between the space complexity and the approximation factor alphain(1/(1-1/e), tildeOmega(sqrtm)] of any single-pass streaming algorithm that estimates the maximum coverage size. Specifically, we show that the optimal space bound is tildeTheta(m/alpha^2). Moreover, we design a single-pass algorithm that reports an alpha-approximate solution in tildeO(m/alpha^2 + k) space. Our algorithm heavily exploits data stream sketching techniques, which could lead to further connections between vector sketching methods and streaming algorithms for combinatorial optimization tasks.