  It is a folklore conjecture that the M\"obius function exhibits cancellation
on shifted primes; that is, $\sum_{p\le X}\mu(p+h) \ = \ o(\pi(X))$ as
$X\to\infty$ for any fixed shift $h>0$. This appears in print at least since
Hildebrand in 1989. We prove the conjecture on average for shifts $h\le H$,
provided $\log H/\log\log X\to\infty$. We also obtain results for shifts of
prime $k$-tuples, and for higher correlations of M\"obius with von Mangoldt and
divisor functions. Our argument combines sieve methods with a refinement of
Matom\"aki, Radziwi\l\l, and Tao's work on an averaged form of Chowla's
conjecture.
