Hi Harry, I would like to help your case. I think it is possible to get your job done within ArcGIS. First of all, which version of ArcGIS you are using?
Let me be clear about your data. Of the two tables, is it that one of the tables contains records (IDs) of the cities on the left of the streets only and other table contains records (IDs) of the cities on the right? Is the ID of a street is same as the IDs of the cities on its both sides? Is my visualization of your data correct?
... was there some smarter way to handle this?
Chopping (or divide and rule) does not always yield better results. You'll have to experiment with an optimum size to divide into. From our experience your results (times) are good enough. Compared to the number of features (40+ millions), 3-4 hours for each process is really good.