The entanglement in operator space is a well established measure for the complexity of the quantum many-body dynamics. In particular, that of local operators has recently been proposed as dynamical chaos indicator, i.e. as a quantity able to discriminate between quantum systems with integrable and chaotic dynamics. For chaotic systems the local-operator entanglement is expected to grow linearly in time, while it is expected to grow at most logarithmically in the integrable case. Here we study local-operator entanglement in dual-unitary quantum circuits, a class of "statistically solvable" quantum circuits that we recently introduced. We identify a class of "completely chaotic" dual-unitary circuits where the local-operator entanglement grows linearly and we provide a conjecture for its asymptotic behaviour which is in excellent agreement with the numerical results. Interestingly, our conjecture also predicts a "phase transition" in the slope of the local-operator entanglement when varying the parameters of the circuits.