Evaluating
    (cl-union (list "foo") (list "foo") :test 'eql)
returns ("foo") but should return ("foo" "foo") instead.

I suggest the following patch.