How to check for multicolinearity between two categorical variables when their contingency table contains many zero entries?

Problem: I have to build a multiple regression model where most of my predictor (independent) variables are categorical (nominal) but I'm running into a few problems due to some of the predictors being (perfectly) colinear.
So I need to check for multicolinearity and remove redundant predictors.

So far I have tried using both a chi-squared test of association and a Fisher exact test between each pair of predictor variables but some of these pairs have contingency tables that contain an abundance of zero entries (entire rows and columns with just zero's) which gives me invalid values for my test statistics and their respective p-values.

Any suggestion for what method/approach/statistical test I can use when checking for multicolinearity in this case?