Great exercise! Here's my solution in Java, seems be about O(n):

    class Ptr {
        public Ptr next;
    }
    
    <T> List<List<T>> mergeIntersecting(List<List<T>> lists) {
        Map<T, Ptr> lookup = new HashMap<>();
        Map<Ptr, List<T>> output = new HashMap<>();
        for (List<T> list : lists) {
            Ptr ptr = new Ptr();
            if (list.isEmpty()) {
                output.put(ptr, new ArrayList<>());
            }
            for (T value : list) {
                Ptr prev = lookup.get(value);
                lookup.put(value, ptr);
                while (prev != null && prev != ptr) {
                    Ptr tmp = prev.next;
                    prev.next = ptr;
                    prev = tmp;
                }
            }
        }
        for (Map.Entry<T, Ptr> entry : lookup.entrySet()) {
            Ptr ptr = entry.getValue();
            while (ptr.next != null) {
                ptr = ptr.next;
            }
            if (!output.containsKey(ptr)) {
                output.put(ptr, new ArrayList<>());
            }
            output.get(ptr).add(entry.getKey());
        }
        return new ArrayList<>(output.values());
    }

If I give it random lists of integers, it takes around 1 microsecond per element of input. Really curious if there's any way to speed it up a lot.