Для этого можно использовать преобразование Schwartzianв Perl:

perl -ne '
   push @A, $_.=<>}{
   print for
    # Schwartzian transform
    map  { $_->[0] }             # recover the line
    sort { $a->[1] <=> $b->[1] } # do the sorting using the key 
    map  { [$_,/_(\d+)M$/m] }    # setup: line(zeroth-indexed) + sorting key(first index)
    @A;                          # operate on elements of array @A
' yourfile

Результаты

>nexus0013_Pseudomonas_53M
.....................................
>nexus0013_Pseudomonas_54M
.....................................
>nexus0013_Pseudomonas_55M
.....................................
>nexus0013_Pseudomonas_57M
.....................................
>nexus0013_Pseudomonas_58M
.....................................
>nexus0013_Pseudomonas_59M
.....................................
>nexus0013_Pseudomonas_60M
.....................................
>nexus0013_Pseudomonas_61M
.....................................
>nexus0013_Pseudomonas_62M
.....................................

поместить файл парами строк в массив @A. Затем в начале мы выполняем маневр Schwartzian, `map -> sort -> map'. При этом мы переносим всю строку + данные сортировки и на последнем этапе маневра восстанавливаем строку после того, как она была отсортирована. Таким образом, в этом случае ключом сортировки является число перед буквой М, лежащее на границе строки. (Помните, мы добавили следующую строку)