We present a novel estimator for map construction in the presence of segregation distortion which is highly computationally efficient. For multi-parental designs this estimator outperforms methods that do not account for segregation distortion, at no extra computational cost. Inclusion of genetic markers exhibiting segregation distortion in a linkage map can result in biased estimates of genetic distance and distortion of map positions. Removal of distorted markers is hence a typical filtering criterion; however, this may result in exclusion of biologically interesting regions of the genome such as introgressions and translocations. Estimation of additional parameters characterizing the distortion is computationally slow, as it relies on estimation via the Expectation Maximization algorithm or a higher dimensional numerical optimisation. We propose a robust M-estimator (RM) capable of handling tens of thousands of distorted markers from a single linkage group. We show via simulation that for multi-parental designs the RM estimator can perform much better than uncorrected estimation, at no extra computational cost. We then apply the RM estimator to chromosome 2B in wheat in a multi-parent population segregating for the Sr36 introgression, a known transmission distorter. The resulting map contains over 700 markers, and is consistent with maps constructed from crosses which do not exhibit segregation distortion.