木工用ボンド自体の選択は間違いではありません。酢酸ビニル系の接着剤は紙や布などの接着にも適していますが、接着に時間が掛かるのは致し方ないでしょうね。紙用のいわゆる糊は湿気を持ったりすると剥がれやすくなるので本棚のような物には向かないでしょう。接着力が強くきわめて短時間で接着できるものとしてはホットボンド(ホットメルト)がありますが、これは熱で樹脂を溶かし柔らかくなったところで張り合わせ、温度が下がればすぐに強度がでるので、接着に要する時間はもっとも短く、しかも強度も十分ですが、樹脂が溶けている間に張り合わせる必要があり、温度が下がってくると樹脂が硬くなってくるので張り合わせ面に隙間が開いてしまう可能性があり、広い面積に塗り広げるような接着には向きません。ダンボール箱の封をするような場合であれば線状に塗布しすぐに張り合わせられるので良いのですが、何点かを同時に張り合わせるような必要があるときは、樹脂の温度を保つために保温したり、ヒートがんで暖めながら行うなどの方法をとらないとうまくいかないでしょう。
簡単に手に入り安価で接着強度もあり、時間的にも比較的短時間ですむものとしては、合成ゴム系の接着剤がいいのではないでしょうか。ホームセンターなどを探せばG17などの製品名で販売されています。使用上の注意としては有機溶剤を含むため換気の良いところで使うことと、可燃性の溶剤を含むので火気の近くでは使わないこと、接着の際には両方の接着面に薄く塗り広げて、しばらく乾かし(手で触ってみてあまりべとつかなくなる程度まで)強く押し付けて接着します。接着剤を塗ってすぐに張り合わせても接着はできますが、強度が出るまでに長い時間が掛かるようになりますし、強度的にも弱くなります。張り合わせるタイミングに慣れが必要ですが、要らない材料で試してみて張り合わせた直後から動かないくらいにつくような状態まで乾かしてからありあわせます。