今後遺留分を請求していこうと考えている

まずは、後妻の方が、（事実上）お父様の遺産がないと主張されるのであれば、お父様名義の預金通帳や最後の住所地の不動産登記簿謄本あるいは借家であれば賃貸借契約書の写しの交付を求めるべきでしょう。
また、お父様の遺言書の開示を求めるべきでしょう（自筆の遺言の場合には、管轄する家庭裁判所での検認といって、確認の手続を行なう必要があります）。遺言書が民法所定の要件を満たしているのか、本当に「後妻の方に全て相続させる」という意味なのか等について、確認する必要があります。
後妻の方が開示に応じない場合は、最後の住所地や元の居住不動産、その他心当たりのある不動産登記簿謄本は法務局へインターネットでも交付請求が可能です。また、預金履歴については、法定相続人として金融機関への開示請求が可能ですので、最後の住所地の近辺その他心当たりのある金融機関へ問い合わせを行なってみるべきでしょう。
弁護士費用については、①着手金は相手方への請求（見込み）金額の数パーセント程度を目安に交渉・調停・訴訟等の手続ごとに、②報酬金は取得金額の１０～１５％程度が一つの目安になるかと思います。その他、③裁判所への印紙代や資料取得費用等の実費や、④交渉とともに資産調査も依頼される場合は着手金計算に当たり考慮させて頂くことになるかと思います。

今後、遺留分減殺請求をされるにあたっては、山本様の遺留分がどれだけあるのかということを確定する必要があります。そのためには、
①　遺言の内容の確認
②　相続人が誰々なのか、の確認
③　相続財産の範囲の確認
　が必要となってきます。

　遺言については、まずその遺言が公正証書遺言なのか、自筆証書遺言なのか、いずれにせよ開示を受けて内容を確認する必要があります。公正証書遺言であれば、遺言作成時に認知症等で遺言能力が失われていない限り、あまり無効になることはありませんが、自筆証書遺言の場合は、法律で形式的な要件が厳格に定まっていますから、無効になる可能性もあります。

　また、「相続手続は全て妻に一任するという内容で、相続となるようなものは無い」という話が不可解です。「手続」を「一任」するということであれば、再婚者を遺言執行者に指定している趣旨かと思われますが、遺言執行者とは「遺言の内容を実現する為に必要な行為や手続をする人」のことですから、その人に「遺産を誰にどれだけ配分するのか」を決める権限はありません。そもそも、「相続となるようなものがない」のであれば、相続の手続も必要ないはずで、先方の話は不自然です。　

　相続人の範囲の調査は、戸籍を取り寄せて行います。
　相続財産の調査は、各財産によって調査方法が異なります。どの財産が遺産にあたるかということ自体に争いがあれば、遺産を確定させるための訴訟を行う場合も有ります（遺産確定の訴え）。

　遺留分減殺請求の通知は、時効期間に注意が必要です。（遺留分減殺請求権は、遺留分権利者が相続開始・減殺すべき贈与・遺贈があったことを知った時から、１年で時効によって消滅します。）早いうちに,配達証明付きの内容証明で通知をしておかれるべきです。

　費用については、弁護士によって区々かも知れませんが、やはり請求金額を基準として、着手金が5％～８％、成功報酬が取得金額の10％～16％程度ではないでしょうか。