Regarding performance, GPUs have dedicated hardware for MSAA which can be quite fast, indeed. However, this hardware has two drawbacks: (a) it's very limited and doesn't cooperate well with modern 3d engines; (b) performance is dependent on the number of polygons in the scene (the more polygons the lower the performance).
MLAA, on the other hand, can be used in every scene and has constant overhead that depends only on the resolution used. Most Xbox360 and PS3 games use variants of MLAA, so we know for a fact that this filter can run on modest hardware at 720p. Intel has also published papers that show the effect running on the CPU in real-time (i.e. render the scene on the GPU, download to the CPU for filtering and re-upload for display).
Without looking at the code or any benchmarks, my guess is that MLAA should be usable on most mid/high-range SM3.0 card and maybe a few high-end SM2.0b cards, provided enough memory bandwidth.