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