It was very interesting, but I could not find any information on how to work with lists like Generic SortedList<> in revers order. In the end all turned out very simple. You need to get a IList<> of keys and use for loop in descending order through that list. Below is a code snippet.
SortedList<int,DgvRowInfo> rowInfoList = null;
...
DgvRowInfo rowInfo;
// walk through the list in revers order
IList<int> keyList = rowInfoList.Keys;
for (int i = keyList.Count - 1; i >= 0; i--)
{
rowInfo = rowInfoList[keyList[i]];
dgvHandler.MoveRow(rowInfo.CurrentRowIndex, rowInfo.NewRowIndex);
}