За время своего учительства, в переездах из губернии в губернию, он собрал множество народных произведений. Поразительно, что труд сей совершался калекой, которому передвижение и писание давались ценой физических страданий (он не мог даже одеться без посторонней помощи, а влезать и слезать с экипажа стоило ему настоящих мучений). Он еле-еле передвигался на костылях, пальцы сведены от ревматизма, записывать трудно – и при этом Шейн обнаруживает самую завидную энергию. В 1868-1870 годах в «Чтениях Общества истории и древностей российских» выходят собранные Шейном песни детские, хороводные, плясовые, скоморошные, беседные, голосовые или протяжные, шутливые, забавные и сатирические, обрядные, свадебные и похоронные причитания и др. Они издаются и в виде отдельной 600-страничной книги: «Русские народные песни» (Ч. 1. М, 1870), с посвящением «неутомимому деятелю на поприще русского слова» В.И. Далю. Сборник включал около тысячи великорусских песен в принятом собирателем календарно-биографическом порядке. «Везде я старался сближаться с народом, – признается Шейн в предисловии, – прислушиваться к его живой своеобразной речи, пользовался всяким удобным случаем для пополнения своего собрания». Он глубоко убежден, что песня до сих пор «остается верной спутницей многотрудной жизни русского человека от колыбели до могилы», и своим расположением материала стремится раскрыть всю биографию и быт крестьянина в последовательном порядке. Свою задачу он видит в том, чтобы познакомить читателей «очень близко со многими сторонами быта русского человека, с его верованиями… с неисчерпаемым богатством его языка, которым он так творчески умеет пользоваться». И, как отмечали исследователи, «искусным подбором песен Шейну удалось воспроизвести типические черты русского национального характера». Интересно, что одна песня из этого сборника «Спится мне, младешенькой» была включена Н.А. Некрасовым в поэму «Кому на Руси жить хорошо».
Рецензируя книгу, академик Я.К. Грот назвал Шейна одним из «самых ревностных» русских собирателей, подарившим науке сборник песен, «собранных на обширном пространстве великой России»; отмечал его необыкновенную преданность делу и удивительную опытность и сноровку в записывании песен. «По богатству содержания этот том, посвященный В.И. Далю, конечно, порадует всех, интересующихся разработкой русской народной поэзии», – резюмировал Я.К. Грот. А Н.И. Костомаров в статье «Великорусская народная поэзия. По вновь изданным материалам» (1872), так писал о Шейне: «Такое лицо, свято и бескорыстно посвятившее себя прекрасному делу, полезному для отечественной науки, достойно того, чтобы помочь ему, а помочь ему можно только одним – даровать ему средства и содействие к продолжению своего дела. Этот человек весь предан ему, любит его более всего в мире, и, несмотря на свои немолодые лета и очень хилое здоровье, готов еще и, конечно, может сделать более десяти молодых и здоровых, с его необыкновенною любовью и неутомимою деятельностью. Дай Бог, чтоб на Руси не переводились такие почтенные труженики, которые, не возносясь высоко, не принимая на плечи свои тягости, которой они нести не могут, работают скромно, но делают столько, сколько сделать в состоянии по своим способностям и обстоятельствам жизни».
Между тем, обстоятельства жизни заставляют его сосредоточиться на учительской профессии: он изучает специальную литературу, ведет наблюдения над языком учащихся, их поведением. Осенью 1865 года Шейн переселился в Витебск и стал преподавателем немецкого языка в городской гимназии; работает он также в местных мужской и женской гимназиях.
Именно в Витебске Павел Васильевич вознамерился собирать белорусский фольклор. Разработал специальную памятку для записи песен, которую назвал «Просьба». Она была тиснута тиражом 600 экз. в Витебской типографии и разослана по Северо-Западному краю (а позднее неоднократно перепечатывалась). По существу это первая фольклористическая инструкция в России! Шейн настаивает здесь на необходимости точного сохранения говора, точного обозначения, к какому роду относится песня, как и от кого, когда и где записана – словом, излагает те требования, которые станут впоследствии общеобязательными для каждого собирателя. Особенно важно впервые установленное им правило повторять записанные песни с пения и говора «во всех его мельчайших оттенках».