MySqlで１テーブルの列が多くなりすぎる場合の設計

アプリケーションで各情報がどの様に扱われるかによって適切な設計は変わりますが、
設計完了までに情報が固まり、あくまで店舗ごとに情報を扱うようなケースであれば、列数は100でも200でも問題にならないと思います。

また、店舗数がそんなに多くないのであれば、列の追加によるインデックスの貼り直しコストもそんなに大きな問題にはならないので、列数を気にしないという方向はありだと思います。

(shop_id, key, value) から成るテーブルを作って列数を減らそうかとも思いましたが 

管理画面から動的に列の変更をしなければならないようなケース以外だとデメリットの方が大きくなると思います。
それならば、項目ごと、出来れば項目の分類ごとにテーブルを用意して、店舗IDをキーにしてjoinするような方法の方がまだいいかなと思いますね。

Entity-Attribute-Valueは確かにアンチパターンとして挙げられているように、テーブルのカラムが少なくなるだけで、データ抽出が難しくなります。
あと程度カラムは増えても仕方ない面もありますが、テーブルを分割すべきときは、1つの店舗に対して複数の値を持つカラムが登場したときには、テーブルを分けましょう。

例えば1つの店舗に対し、複数の電話番号やFAX番号を持つことはありますよね。そういう場合は電話番号テーブルを作成して、店舗を一意に決定するコード値で関連付けする…といった設計になるでしょう。

質問文を見る限り抵触してはいなさそうですが、例えば複数の電話番号を管理するのに「tel1,tel2,tel3」のようにカラムを増やしているなら、これはマルチカラムアトリビュートのアンチパターンになります。
そうでないならば、他の方もおっしゃっていますが50項目程度なら特に問題にならないと思います。

ただ大半の店舗には不要でNullが設定されるカラムばかりが多いなら
全ての店舗に共通して入力必須な項目と、一部の店舗のみに必要な項目はテーブルを分けるのも良いかも知れません。
その際も、その2つのテーブルの項目数が同じ50程度になるように分けるので良いと思います。

必要なら作るしかないと思いますが…
項目一覧がわかれば、それを評価してくれる
詳しい方はいるかと。