The proofs rely, in the background, on Urysohn's Lemma, which follows from the Principle of Dependent Choices but is not provable without some Choice. It is false in the ordered Mostowski model, see
Geordnete Läuchli Kontinuen by N. Brunner.
More information can be found in Versions of normality and some weak forms of the axiom of choice by Howard, Keremedis, Rubin, and Rubin; the link is to the review on zbMath, the paper is behind a paywall.

**Addendum** In metric spaces one can *define* Urysohn functions, but there one runs into a difficulty with paracompactness: in On Stone’s theorem and the Axiom of Choice Good, Tree, and Watson prove that the paracompactness of metric spaces does not follow from the principle of Dependent Choices.

**Summary** For separable metric spaces the existence of partitions of unity can be proven without Choice, because locally finite refinements can be constructed from countable refinements, and because the continuous functions needed can be defined from the metric.
In arbitrary metric spaces the proof of paracompactness needs a certain amount of choice, and in arbitrary paracompact spaces one needs choice twice: first in the proof of Urysohn's Lemma and second in the choice of a set of Urysohn functions that will yield the partition of unity.