Non-Euclidean data that are indexed with a scalar predictor such as time are increasingly encountered in data applications, while statistical methodology and theory for such random objects are not well developed yet. To address the need for new methodology in this area, we develop a total variation regularization technique for nonparametric Fréchet regression, which refers to a regression setting where a response residing in a generic metric space is paired with a scalar predictor and the target is a conditional Fréchet mean. We show that the resulting estimator is representable by a piece-wise constant function and investigate the convergence rate of the proposed estimator for data objects that reside in Hadamard spaces. The method can also be applied to the problem of estimating multiple change-points in a sequence of non-Euclidean data. This is illustrated via the application to modeling the dynamics of brain networks and the study of evolving mortality distributions endowed with the Wasserstein distance.