You can get Reduce[] to break down the Abs[] like Bill Nelson, although it will produce seven cases instead of four. You also have to set up the function range system yourself.

LogicalExpand@ Reduce[ (* break down function *)
     {k == Abs[x1 + y1 - 1]/Sqrt[2] + Abs[x2 + y2 - 1]/Sqrt[2]},
     {x1, y1, x2, y2}, Reals
     ] //
   Map[
    Reduce[ (* add constraints; eliminate {x1, y1, x2, y2} *)
      {#, x1^2 + y1^2 == 1, x2^2 + y2^2 == 1, x1 x2 + y1 y2 == 1/2},
      {k}, {x1, y1, x2, y2}, Reals] &
    ] // FullSimplify // (* simplify the many intervals *)
 Reduce[#, k] & (* optional output as a compound inequality *)
(*  1/4 (-Sqrt[2] + Sqrt[6]) <= k <= Sqrt[2] + Sqrt[3]  *)

Even though the correct maximum value was obtained by modifying the code, the entire range of k is still incorrect.

There's an error in the maximum value obtained from the code. The correct maximum value is √2 + √3.

I would switch to polar coordinates:

original = {RealAbs[x1 + y1 - 1]/Sqrt[2] +
    RealAbs[x2 + y2 - 1]/Sqrt[2],
   x1^2 + y1^2 == 1, x2^2 + y2^2 == 1,
   x1 x2 + y1 y2 == 1/2};
polar = {x1 -> Cos[t], y1 -> Sin[t],
   x2 -> Cos[u], y2 -> Sin[u]};
new = Join[original /. polar // Simplify,
  {0 <= t <= 2 Pi, 0 <= u <= 2 Pi}]
f[t_] = Piecewise[new[[1]] /.
    Solve[Rest[new], u, Reals] /.
   ConditionalExpression -> List]
Plot[f[t], {t, 0, 2 Pi}]
FunctionRange[{f[t], 0 <= t <= 2 Pi}, t, k]
Map[Simplify, %]
%% // N

That's a clever approach, but relying on this single transformation alone leads to an incorrect result.