This is not an editorial issue; it needs to go to LWG.

Should I create an issue here issues.isocpp.org ?

I believe this issue is incorrect. Remember that either range can contain duplicate elements. Consider:

int haystack[] = {1};
int needles[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
includes(begin(haystack), end(haystack), begin(needles), end(needles));

Clearly we cannot give a complexity bound better than last2 - first2 comparisons.

See http://lists.isocpp.org/lib/2018/05/7092.php; includes is actually checking for subsequence-ness. Once you exhaust haystack there's no point going through the rest of needles.

The complexity requirements are consistent with the current description, and should be fixed if/when the description is fixed to actually describe what the algorithm is "supposed' to do. Seems like LWG is already on the case. I'll reply to that lib thread to request that the complexity be revisited when the spec is fixed.