This doesn't work because $page->children is an array of pages (PageArray), not a Page. Think of it like a boat carrying a bunch of people. The boat can't have children, but the people in it can.
I'm also not sure $page->children->children would be all that useful, because they would have lost all sorting context. However, I'm only thinking in context of the sites I make and know everyone has different needs. So if you want to have something equivalent to $page->children->children, it would be $page->find('id>0'). But I would suggest using Soma's examples as they are more specific to a template, and it's better to be specific.
Nearly any search that gets passed through a selector is fully indexed, so it doesn't have to scan the whole site. If you put in "template=video" it [mysql] heads straight to an index of pages with the video template, so it's not scanning or considering other pages.
You'd want to limit that if you were using the video template elsewhere in the site and didn't want videos from one branch getting mixed in with videos from another. However, if you know where you are using the video template and aren't going to be using it on other branches in the site, there's no speed advantage to performing the search within a parent $page rather than just using $pages->find() to do it. Technically, there's slightly more [minor] overhead doing a $page->find() than a $pages->find() because it's adding a lookup table to the search that may or may not need to be there.