It's just an index on the transaction id fields of the rows, so it should scale like any other index on the table.
Indexes in postgres point to the page, not the tuple. The VM keeps two bits per page: "does this page have any 'dead' tuples?", and "does this page need to be touched for xid wraparound?"
Vacuuming doesn't touch a page unless the VM indicates it's necessary.
Except for BRIN.