Turbulence is the dominant source of collisional velocities for grains with a wide range of sizes in protoplanetary disks. So far, only Kolmogorov turbulence has been considered for calculating grain collisional velocities, despite the evidence that turbulence in protoplanetary disks may be non-Kolmogorov. In this work, we present calculations of grain collisional velocities for arbitrary turbulence models characterized by power-law spectra and determined by three dimensionless parameters: the slope of the kinetic energy spectrum, the slope of the auto-correlation time, and the Reynolds number. The implications of our results are illustrated by numerical simulations of the grain size evolution for different turbulence models. We find that for the modeled cases of the Iroshnikov-Kraichnan turbulence and the turbulence induced by the magneto-rotational instabilities, collisional velocities of small grains are much larger than those for the standard Kolmogorov turbulence. This leads to faster grain coagulation in the outer regions of protoplanetary disks, resulting in rapid increase of dust opacity in mm-wavelength and possibly promoting planet formation in very young disks.