You can just write
verify(service).perform((Collection<String>) Matchers.argThat(contains("a", "b")));
From the compiler’s point of view, this is casting an Iterable<String> to a Collection<String> which is fine, because the latter is a subtype of the former. At run time, argThat will return null, so that can be passed to perform without a ClassCastException. The important point about it is that the matcher gets onto Mockito’s internal structure of arguments for verification, which is what argThat does.