Hi @kees_v -- I gave this a try with simulated data with the volumes you mentioned and had quite good performance with the SpatialRelator on FME 2018. I'm curious what build of FME you were using, and how many attributes are on the feature classes? I used the Grid features as the Requestor.

I also turned off all attribute accumulation in the SpatialRelator -- the count you seek is the _related_candidates attribute that gets added. I used "Intersects" as the predicate.
If you are on 32 bit and can't go to 64, I can imagine this could cause issues. A workaround is to:
a) translate your lines to FFS -- with a spatial index
b) make a workspace with your grid as the input. Run each feature through a FeatureReader saying "Intersects" as the spatial predicate and pointing to the FFS file you just made. The "Initiator" port is what you want to catch on the output side == it will have the count of features that matched added.
c) run it with a small data volume to test -- limit the grids by adjusting the max features to read parameter in the navigator https://docs.safe.com/fme/html/FME_Desktop_Documentation/FME_Workbench/Workbench/reader_parameters_featuresToRead.htm (don't forget to unset this once everything looks good).
Hope this helps. Really good question here and one we want ot make ever better moving forward.