Having the ability to grant all wishes and being powerful why does Shenron have to be afraid of Bills in the movie Dragon Ball Z: Battle Of The Gods?
If you don't recall the Dragons that are created by the Dragonballs are only as powerful as the person who created them. This means that Shenron is not all powerful and cannot grant a wish outside of the power of their creator, an example would be wishing to destroy Freiza when Kami was the creator. Dragons from the Dragonballs can grant any wish as long as it's within their creator's power... this means a being more powerful than the creator of them cannot be destroyed by the Dragon and the Dragon can be destroyed by that being.
Dragonball Wiki Excerpt:
Shenron can bestow any wish as long as it does not exceed the power of his creator, who must be still alive (i.e. Kami/Piccolo or Dende).
During Battle of the Gods this means that Dende is the current creator of the Dragonballs, which means that any being more powerful than Dende could defeat Shenron...
Shenron actually does not have the power to grant all wishes. He can't bring you back from the dead twice, he can't wish the Saiyans away in the first saga.
He can do things that no one else is able to do, but he's not actually all powerful.
And apparently he's less powerful than Bills, and he knows it.
In Dragon Ball, Shenron was once killed by King Piccolo. If someone evil but way less stronger than Beerus can kill Shenron, it makes sense Shenron to be afraid of Bills the god of destruction and most powerful being in the universe after Wiss