If this card is destroyed when its original owner does not have control of it, the effect does not activate.
The effect to return to the Deck when is destroyed by the opponent and sent to the Graveyard will activate even during the Damage Step. The effect will also activate even if is destroyed in battle by an opponent's monster.
Even if the effect of "Necrovalley" is applied, the "When this card you control is destroyed by your opponent's card (either by battle or by card effect) and sent to your Graveyard: Shuffle this card into your Deck." effect of "Madolche Mewfeuille" is not negated and it returns to the Deck.