Aczel-Mendler bisimulations are a coalgebraic extension of a variety of computational relations between systems. It is usual to assume that the underlying category satisfies some form of the axiom of choice, so that the collection of bisimulations enjoys desirable properties, such as closure under composition. In this paper, we accommodate the definition in general regular categories and toposes. We show that this general definition: 1) is closed under composition without using the axiom of choice, 2) coincides with other types of coalgebraic formulations under milder conditions, 3) coincides with the usual definition when the category satisfies the regular axiom of choice. In particular, the case of toposes heavily relies on power-objects, for which we recover some favourable properties along the way. Finally, we describe several examples in Stone spaces, toposes for name-passing, and modules over a ring.