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. By sharp contrast, the ground state in this regime evolves smoothly with increasing interaction analogous to the BCS-BEC crossover.