We analyze the fragmentation behavior of random clusters on the lattice under a process where bonds between neighboring sites are successively broken. Modeling such structures by configurations of a generalized Potts or random-cluster model allows us to discuss a wide range of systems with fractal properties including trees as well as dense clusters. We present exact results for the densities of fragmenting edges and the distribution of fragment sizes for critical clusters in two dimensions. Dynamical fragmentation with a size cutoff leads to broad distributions of fragment sizes. The resulting power laws are shown to encode characteristic fingerprints of the fragmented objects.