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]  *)

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

Awesome, the question is now crystal clear. Thank you so much!

Based on the symmetry of the circle, modifying the code as follows will yield the correct answer.

FunctionRange[{-(x1 + y1 - 1)/Sqrt[2] - (x2 + y2 - 1)/Sqrt[2], 
  x1^2 + y1^2 == 1, x2^2 + y2^2 == 1, x1 x2 + y1 y2 == 1/2, 
  x1 + y1 - 1 <= 0, x2 + y2 - 1 <= 0}, {x1, y1, x2, y2}, k]

Your method was brilliant; it perfectly solved the problem and even plotted the function graph. The parametric equation approach was very clever. Thank you so much!

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