Thank you for opening the issue. One would need to profile the implementation to see what the slow parts are to move forward on this issue.

Performed a high-level analysis and found that in a sample of 6000 records, 99% of the time is taken by sklearn.metrics.cluster._expected_mutual_info_fast.expected_mutual_information

System:
    python: 3.9.7 (default, Sep 16 2021, 08:50:36)  [Clang 10.0.0 ]
executable: /Users/kshitijmathur/opt/anaconda3/bin/python
   machine: macOS-10.16-x86_64-i386-64bit

Python dependencies:
      sklearn: 1.1.3
          pip: 22.2.2
   setuptools: 58.0.4
        numpy: 1.22.4
        scipy: 1.7.1
       Cython: 0.29.24
       pandas: 1.4.3
   matplotlib: 3.4.3
       joblib: 1.1.0
threadpoolctl: 2.2.0

Built with OpenMP: True

almost entire performance degradation is coming from this line of code
start = np.array([[v - N + w for w in b] for v in a], dtype='int')
https://github.com/scikit-learn/scikit-learn/blob/main/sklearn/metrics/cluster/_expected_mutual_info_fast.pyx#L53

For 6000 records,
above line takes 125 seconds
The for nested loop at the end of Cython function takes ~25 seconds

So to me, since the time complexity of above line of code is O(N^2), then we can't actually expect linear increases in runtime.
I'm not an expert in Cython, but I will try to see if something can be done about this.