We have conducted the first comprehensive numerical investigation of the relative velocity distribution of dust particles in self-gravitating protoplanetary discs with a view to assessing the viability of planetesimal formation via direct collapse in such environments. The viability depends crucially on the large sizes that are preferentially collected in pressure maxima produced by transient spiral features (Stokes numbers, St ∼ 1); growth to these size scales requires that collision velocities remain low enough that grain growth is not reversed by fragmentation. We show that, for a single-sized dust population, velocity driving by the disc's gravitational perturbations is only effective for St > 3, while coupling to the gas velocity dominates otherwise. We develop a criterion for understanding this result in terms of the stopping distance being of the order of the disc scaleheight. Nevertheless, the relative velocities induced by differential radial drift in multi-sized dust populations are too high to allow the growth of silicate dust particles beyond St ∼ 10- 2 or 10-1 (10 cm to m sizes at 30 au), such Stokes numbers being insufficient to allow concentration of solids in spiral features. However, for icy solids (which may survive collisions up to several 10 m s-1), growth to St ∼ 1 (10 m size) may be possible beyond 30 au from the star. Such objects would be concentrated in spiral features and could potentially produce larger icy planetesimals/comets by gravitational collapse. These planetesimals would acquire moderate eccentricities and remain unmodified over the remaining lifetime of the disc.