The orbital speed of Mars is about 24 km/sec or ~ 2 million km/day, and so relative velocity to an asteroid could be fairly slow for one in a similar orbit, or easily 1 million km/day or more for one in a weird orbit.
Optical (Visual, thermal IR)
You could set up several optical (visible or thermal IR) survey telescopes around Mars, and try to vigilantly scan the most celestial sphere (except for directions near the Sun) for unexpected, very dim objects moving unpredictably, but that's quite a challenge, and there's still the big blind spot anywhere in the general direction of the Sun.
A better way is to start looking now! For potential NMO's (near-Mars-objects) you would start looking now, or at least several years before you started to need the information. And you would look using a space telescope with an orbit closer to the Sun than Mars for two reasons:
With a different period than Mars, the object will approach close to you within a few orbits. The synodic period $\frac{1}{T_S} = \left(\frac{1}{T_1} - \frac{1}{T_2} \right) $ is fairly short when the two periods are significantly different.
With the target objects farther from the Sun than you are, their close approaches happen when they are in the night sky, so you don't have the Sun to worry about.
Number 2. is important because it means you can shield your telescope from the Sun's heating effects as well as from the light. You want to keep an asteroid-hunter's telescope's cryogenic optics and sensors very cold.
It turns out that it's easier to search for these trouble-makers in the thermal infrared than it is in visible light. They are fairly black (albedo's often from 0.05 to 0.1) and reflect direct sunlight poorly. But that means that they absorb most of the Sun's light and effectively radiate it in thermal infrared. But the only way to have a telescope sensitive to thermal IR is to have the entire telescope (mirrors and optics and sensors) very cold so that the thermal radiation of the distant asteroid isn't swamped by thermal IR from the telescope itself.
Most stars (but not all objects) are much dimmer in thermal IR than they are in the visible, so that could potentially help when sorting out asteroids versus stars in preprocessing, compared to visual surveys.
Source: NEOCam: Finding Asteroids Before They Find Us (Orbit)
For more about WISE, NeoWISE, NEOCam (now NEO Surveyor), and B612, see:
Radar, Lidar
You might consider searching using Radar (similarly to the way space debris is monitored) but you'd dismiss it quickly. The Sun paints objects between here and Mars with 0.5 to 1.3 kilowatts per square meter, and at a million kilometers you won't be able to match that with radar or even Lidar, at least not for the foreseeable future.
Another way this is often expressed is that the strength of signals using optical detection varies as $1/r^2$ whereas for radar (where you have a round-trip) it varies as $1/r^4$.
