We consider the algebra of Hecke correspondences (elementary transformations at a single point) acting on the algebraic K-theory groups of the moduli spaces of stable sheaves on a smooth projective surface S. We derive quadratic relations between the Hecke correspondences, and identify the algebra they generate with a generalized shuffle algebra. This allows us to define a universal shuffle algebra, which acts on the above-mentioned K-theory groups for any surface S, via a suitable specialization of parameters.