> 128 bit address space is overkill, but I wonder if a hardware-backed 128 bit integer type would be useful for bit twiddling - or whether spreading the bits over two 64-bits integers is 'good enough' assuming that both halfs reside in the same cache line, and it's unlikely that a single bit twiddling operation needs to affect both halfs.

Don't we already have that? My reading of https://en.wikipedia.org/wiki/Advanced_Vector_Extensions is that AVX starts at 128-bit and goes up from there.