This submodularity property is known to not hold, as the OP has found out already. However, I'd like to mention the following observation:

Let $f$ be defined on $(0,\infty)$ such that $-f'$ is operator monotone (i.e., for $A\le B \implies f'(A) \ge f'(B)$), then \begin{equation*} \text{Tr}\, f(A+B+C)+\text{Tr}\, f(A) \le \text{Tr}\, f(A+B)+\text{Tr}\, f(A+C). \end{equation*}

Example: the above inequality holds for $f(t)=t^p$ for $p\in (0,1)$.

This submodularity property is known to not hold, as the OP has found out already. However, I'd like to mention the following observation:

Let $f$ be defined on $(0,\infty)$ such that $-f'$ is operator monotone (i.e., for $A\le B \implies f'(A) \ge f'(B)$), then \begin{equation*} \operatorname{Tr} f(A+B+C)+\operatorname{Tr} f(A) \le \operatorname{Tr} f(A+B)+\operatorname{Tr} f(A+C). \end{equation*}

Example: the above inequality holds for $f(t)=t^p$ for $p\in (0,1)$.

This submodularity property is known to not hold, as the OP has found out already. However, I'd like to mention the following observation:

Let $f$ be defined on $(0,\infty)$ such that $-f'$ is operator monotone (i.e., for $A\le B \implies f'(A) \ge f'(B)$), then \begin{equation*} \text{trace} f(A+B+C)+\text{trace} f(A) \le \text{trace}f(A+B)+\text{trace}(A+C). \end{equation*}

Example: the above inequality holds for $f(t)=t^p$ for $p\in (0,1)$.

This submodularity property is known to not hold, as the OP has found out already. However, I'd like to mention the following observation:

Let $f$ be defined on $(0,\infty)$ such that $-f'$ is operator monotone (i.e., for $A\le B \implies f'(A) \ge f'(B)$), then \begin{equation*} \text{Tr}\, f(A+B+C)+\text{Tr}\, f(A) \le \text{Tr}\, f(A+B)+\text{Tr}\, f(A+C). \end{equation*}

Example: the above inequality holds for $f(t)=t^p$ for $p\in (0,1)$.