Да не было в СССР конных дивизий в природе! Были кавалерийские. При этом в войсках ОГПУ-НКВД-МВД - ни одной, а только кавалерийские полки в составе пограничных и оперативных/внутренних войск.
В данном конкретном случае, те кто Вам подсказал, имели, наверное, в виду части конвойных войск НКВД-МВД СССР.
Для начала сделайте запрос в региональное ГУВД-УВД тогдашнего (на период службы) проживания Вашего прадеда. Если он проходил службу в органах правопорядка, то здесь на него отыщется, как минимум, УПК - учётно-послужная карта.
Если же он всё-таки из войск ОГПУ-НКВД, то без наличия на руках номера части по месту службы вести поиск во многом заведомо безрезультатно...