Motivated by recent observations of superfluidity of ultracold fermions in optical lattices, we investigate the stability of superfluid flow of paired fermions in the lowest band of a strong optical lattice. For fillings close to one fermion per site, we show that superflow breaks down via a dynamical instability leading to a transient density wave. At lower fillings, there is a distinct dynamical instability, where the superfluid stiffness becomes negative; this evolves, with increasing pairing interaction, from the fermion pair breaking instability to the well-known dynamical instability of lattice bosons. Our most interesting finding is the existence of a transition, over a range of fillings close to one fermion per site, from the fermion depairing instability to the density wave instability as the strength of the pairing interaction is increased.