You have to use full screening to prevent the interference (and even that may not be enough). So find a cable with two of more wires inside a braided screen - the screen is connected to Arduino ground (do NOT connect to the vehicle chassis except via the Arduino, or you'll have a ground loop). At the hall-sensor end keep the wiring that's outside of the screen as short as possible.
This ought to reduce the pickup you've been experiencing a lot... Remember your HT leads are carrying a 30kV signal so even tiny amounts of stray capacitance will inject a lot of signal into nearby wiring unless its screened. For some stupid reason the HT leads on an engine are not themselves screened (which would be an obviously better solution).