Problems that include Abs or Conjugate often seem more difficult to solve.
If you could find a way to express the problem in a form similar to
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]
then you can instantly get a solution. Then you will need to handle the other three cases and combine those results to try to get a complete solution.
